logo标签列表

骑士们有没有办法坐在圆桌旁，以便每个骑士都能坐在他的朋友旁边？

c++graphcycle
3
我在做一些编程挑战时遇到了这个问题：
圆桌位于一个巨大的大厅中，由N把椅子围成一圈。每个骑士都想坐在他的朋友旁边，否则他就拒绝坐下。
第一行给出了一个整数n，其中n是圆桌骑士的数量（3<=n<=100）。骑士从1到n编号。
接下来的n行中，每行包含一个由0或1组成的长度为n的序列，以空格分隔。第i个序列表示第i个骑士的友谊关系。第j个值确定第i个骑士是否是第j个骑士的朋友。如果值为1，则它们是朋友；如果值为0，则它们不是朋友。
由于友谊是互相的，如果i是j的朋友，那么j也是i的朋友。
输出
如果骑士们可以围坐在圆桌周围，则显示“YES”，否则显示“NO”。
据我所理解，我们被给予的是一个邻接矩阵，实际上是一个无向图，其中节点是骑士，边表示友谊关系。现在我的想法是在图中搜索一个长度为N的循环，或者说是一个哈密顿循环。如果是这种情况，输出YES，否则输出NO。
我的代码在提供的基本示例中是有效的，但在某些测试中，当N变得足够大时，它会出现错误。请注意，这是一个错误的答案，而不是时间限制错误。
这是我的代码：
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

void dfs_search(vector<vector<int> > &matrix, vector<bool> &visited, int node, int parent, int n, int path, bool &found){
    if(found)
        return;
    else if(visited[node] && node == parent && path == n){
        found = 1;
        return;
    }
    else if(visited[node])
        return;
    else{
        visited[node] = 1;
        path++; 
        //cout<<node<<" "<<path<<endl;
        
        for(int i=0; i < n; i++){
            if(matrix[node][i] == 1){
                dfs_search(matrix, visited, i, parent, n, path, found);
            }
        }

        visited[node] = 0;
        path--;
    }

}
int main(){

    int n;

    cin >> n;

    bool found = 0;

    vector<vector<int> > matrix(n, vector<int>(n));
    vector<bool> visited(n, 0);

    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++)
            cin>>matrix[i][j];
    }

    for(int i=0; i<n; i++){
        dfs_search(matrix, visited, i, i, n, 0, found);
        if(found){
            break;
        }
    }
    
    if(found)
        cout<<"YES";
    else
        cout<<"NO";

    return 0;
}

我是否遗漏了一些非常明显的东西，导致我的代码在更大的输入下失败？或者我是否遗漏了需要处理的特殊情况？
我会非常感谢任何提示。提前谢谢！
示例输入：
5 0 1 1 0 1 1 0 0 1 1 1 0 0 1 1 0 1 1 0 1 1 1 1 1 0
示例输出：
是的
3
我是否忽略了一些非常明显的东西，导致我的代码在更大的输入上失败？当你的代码在更大的输入上运行时，可能会因为内存不足或递归过深而失败。你的代码是否表现出这些症状？我敢打赌不会。为什么一个函数、数据结构等在处理50个项目时能正常工作，但在处理100个项目时失败呢？它不应该失败，因此问题不应该出在输入的大小上，而是你没有正确处理某个特殊情况。 - undefined
1
顺便提一下：你正在寻找一个循环。因此，你可以假设第一个座位被第一个骑士占据（在主循环中 i = 0）。 - undefined
请编辑您的问题以澄清“near”实际指的是什么。 - undefined
不知道什么是“自环”。最好的猜测是你指的是一个比n更短的循环。你发布的例子中有这样的循环。你的代码似乎处理得很好。 - undefined
你为什么在main里多次调用dfs_search？如果存在哈密顿回路，你可以从任意顶点开始找到它；从第0个顶点开始和其他任何顶点一样好。 - undefined
显示剩余12条评论
1个回答
0
一般来说，最好使用标准库来处理图形。如果每次都从头开始编写顶点和边的数据结构，你会错过效率，并且会花费大量时间来调试图形结构，而不是算法。
一般来说，我避免使用递归函数，因为它们在处理大型图形时不具有可扩展性。但在这种情况下，递归函数非常方便，可以跟踪路径长度，所以我们继续使用它。重要的是要尽量减少递归函数的参数，以免耗尽堆栈内存。因此，将递归函数设为类方法，并将尽可能多的参数移动到类属性中。
就像这样：
#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
#include "cGraph.h" // https://github.com/JamesBremner/PathFinder

class cSeatFinder
{

public:
    void generateExample1();

    void arrangeSeating();

private:

    raven::graph::cGraph g;

    std::vector<bool> visited;

/**
 * @brief Determine if the there is a cycle that includes every node
 * 
 * @param node current node being explored
 * @param pathlength length of path to current node from start
 * 
 * Recursive.  Assumes starting node has id 0
 * 
 * If full cycle found, throws an exception std::runtime_error("found seating");
 * If not found, returns to caller
 */
    void dfs_full_cycle(
        int node,
        int pathlength);
};

void cSeatFinder::generateExample1()
{
    g.add(0, 1);
    g.add(0, 2);
    g.add(0, 4);
    g.add(1, 3);
    g.add(1, 4);
    g.add(2, 3);
    g.add(2, 4);
    g.add(3, 4);
}

void cSeatFinder::dfs_full_cycle(
    int node,
    int pathlength)
{

    // check if we have returned to the start
    if ( node == 0 ) {
        
        // check if we have visited every node
        if( pathlength == g.vertexCount()) {

            throw std::runtime_error("found seating");
        }
    }

    if (visited[node])
        return;

    visited[node] = 1;
    pathlength++;

    for (int vi : g.adjacentOut(node))
        dfs_full_cycle( vi, pathlength );

    visited[node] = 0;
    pathlength--;
}
void cSeatFinder::arrangeSeating()
{
    visited.resize(g.vertexCount(), false);
    try
    {
        dfs_full_cycle( 0, 0 );
    }
    catch (std::runtime_error &e)
    {
        if (e.what() == std::string("found seating"))
        {
            std::cout << "YES\n";
            return;
        }
    }

    std::cout << "NO\n";
}

main()
{
    cSeatFinder theSeatFinder;

    theSeatFinder.generateExample1();

    theSeatFinder.arrangeSeating();

    return 2;
}
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接