我有一个矩阵，每个单元格都有一个布尔属性。我需要确定一个循环，从一个布尔属性为 false 的单元格开始，并且这个循环必须只包含将该布尔属性设置为 true 的单元格（显然，起始单元格除外）。另一个条件是循环中任意两个连续的单元格必须在同一行（或同一列），并且循环中的三个连续单元格不能在同一行（或同一列）。您实际上可以从一个单元格跳到另一个单元格，它们不必是邻居，它们只需要在同一行或同一列上。谢谢你。
问问题
191 次
1 回答
0
更新：我错过了在两个相邻单元格之间不需要移动 - 这增加了每一步可能移动的数量，但并没有真正改变总体思路。
最简单的实现可能是深度优先搜索——你从起始单元开始并查看所有可能的移动——除了第一步之外，最多有三个可能的移动。对于每个可能的移动，您递归地执行相同的操作，直到您再次到达起始单元格或没有可能的移动剩余。在后一种情况下，您追溯一个移动并尝试下一个可能性，如果还有一个剩余。
您必须将最后一次移动的方向与递归调用一起传递，因为该方向对下一步无效。如果不允许多次访问单元格，您也必须跟踪访问过的单元格，并在回溯时取消标记它们。如果允许多次访问单元格，则必须跟踪之前访问单元格时离开单元格的方向，以避免循环。
使用呼吸优先搜索而不是深度优先搜索将避免尝试没有解决方案的长路径，代价是保留大量部分解决方案。A* 搜索可能是加快此速度的另一种选择。
旁注： 多次访问一个单元格可能没有任何价值，因为您可以在第一次访问该单元格时直接采取另一个动作。例外是第一次进入牢房时不允许移动，但我不确定这样的路径是否可行。
于 2013-01-10T20:23:16.000 回答