所以我得到了这个作业，但我不确定如何处理。我得到了一个二维数组，其中一些单元格被禁止访问。然后我需要遍历整个数组选择最长的路线而不进入禁止的单元格。我也不能“回去”再转一圈，遍历应该总是“前进”。输出应该是访问的单元格的数量和正确的顺序。该算法应该具有很大的可扩展性，至少对于具有 100x100 单元格的阵列而言是这样。下面是一张显示任务的图片。
如上图所示，实际上只有两种解决方案:要么沿着边缘向下走一个单元格，然后再次向上，就像示例一样。或者它可能只是沿着完整的边缘。访问的单元格数应该仍然相同； 12.
现在我对此进行了大量搜索并发现了许多变体，据我了解，我应该能够使用 Djikstras、Bellman-Ford、A* 算法或某种深度/广度优先图遍历。但我完全被困住了，不知道从这里去哪里。
最佳答案
这个问题是NP难的，如A. Itai, C. Papadimitriou, J. Szwarcfiter, Hamiltonian paths in grid graphs所示.所以不存在精确的多项式时间算法。
在实践中，你的尺寸问题应该可以通过现代 Constraint Solvers 解决.如何制作方法的回顾Constraint Problem最长路径搜索可以在 Q. Pham, Y. Deville, Solving the Longest Simple Path Problem with Constraint-Based Techniques 找到.
关于algorithm - 在二维数组中查找最长的路线，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/40449326/