查找覆盖所有检查点的路径

我有一个大小为2*N的矩阵A数组，每个元素为*检查点或X危险点不允许进入危险点。查找覆盖所有检查点的路径

您需要查找是否有exist a path覆盖所有检查点而不访问危险点，并且每个点都是visited once。

你可以在任何检查站开始你的旅程。

对于前：

*X** 
***X

路径存在访问所有的检查站。

我的方法：

选择第一检查站从0遇到到N：

如果你在index i和其它阵列（A [0]或A [1]）包含了chekpoint所以如果可能的话，切换数组，如果不在相同的数组中继续。

最后检查是否访问了所有检查点。

我的做法是不给我正确的答案有什么错在这里

代码：

dfs(int x , int i){ 
    Visted[x][i] = true; 
    if(!Visted[x^1][i] && A[x^1][i] == '*') 
     dfs(i, x^1); 
    else if(i+1 < n && A[x][i] == '*') 
     dfs(i+1,x); 
}

来源

2017-05-28 Regression

目前还不完全清楚“每个点访问过一次”。这是否应该是“每个观察点不超过一次”？ –

@ n.m。也许它意味着“恰好一次”。 – Gassa

@ n.m。每个点应该只访问一次 – Regression

正如你所看到的，一旦你选择了初始点，通过你的算法解决方案或者是独特的或者不存在，因为它最多只有一个步骤来尝试每个单元格。

所以，问题可能出在你没有显示的部分：你如何选择初始点？使用此算法，您可以尝试这两种情况，并查看是否有一个结果路径覆盖了每个单元格。

这里有两个例子。在左边，我们必须从第一行开始。在右边，我们必须从第二行开始。

*X 1X     ** 23 
** 23     *X 1X

来源

2017-05-28 08:48:36 Gassa

但我的'DFS'功能似乎是正确的？ – Regression

@JohnySins这可能是对的，但很难说没有上下文。例如，什么是x的范围，什么是n，坐标从零开始还是从一开始，最初调用的函数如何。这是[完整的示例]（https://stackoverflow.com/help/mcve）将解决的问题。 – Gassa

我的算法在两个测试用例上都是正确的。不知道什么错误？ – Regression

查找覆盖所有检查点的路径

回答

相关问题