algorithm - 确定矩阵中的循环

Question

我有一个矩阵，每个单元格都有一个 bool 属性。我需要确定一个循环，从具有 bool 属性 false 的单元格开始，并且此循环必须仅包含将该 bool 属性设置为 true 的单元格(显然，起始单元格除外)。另一个条件是循环中任意两个连续的单元格必须在同一行(或同一列)，并且循环中三个连续的单元格不能在同一行(或同一列)。您实际上可以从一个单元格跳到另一个单元格，它们不必是邻居，它们只需要在同一行或同一列即可。谢谢。

Answer 1

更新:我错过了不需要在两个相邻单元格之间移动的情况 - 这增加了每一步可能移动的数量，但并没有真正改变总体思路。

最简单的实现可能是 depth-first search - 您从起始单元格开始并查看所有可能的移动 - 除了第一步外，最多有三个可能的移动。对于每一个可能的移动，你都递归地做同样的事情，直到你再次到达起始单元格或者没有可能的移动剩余。在后一种情况下，您会追溯一个步骤并尝试下一个可能性(如果还有一个可能性)。

您必须在递归调用时传递最后一步的方向，因为该方向对于下一步是无效的。如果不允许多次访问单元格，则还必须跟踪访问过的单元格，并在返回时取消标记它们。如果允许多次访问单元格，则必须跟踪之前访问单元格时离开单元格的方向以避免循环。

使用 breath-first search而不是深度优先搜索将避免尝试以保留大量部分解决方案为代价的没有解决方案的长路径。 A* search可能是另一种加快速度的选择。

旁注:多次访问一个单元格可能没有任何值(value)，因为您可以在第一次访问该单元格时直接采取其他步骤。异常(exception)是第一次进入单元格时不允许移动但我不确定这样的路径是否可行。