在网格中查找具有特定值的连接块

Question

我无法找到解决我的问题的算法。

我有一个 8x8 块的网格，每个块的值范围从 0 到 9。我想找到与总值匹配的连接块的集合，例如 15。我的第一个方法是从边界开始，即工作得很好。但是当从网格中间开始时，我的算法就会丢失。

有人知道一个简单的算法可以使用吗？或者你能给我指出正确的方向吗？

谢谢！

Answer 1

据我所知，没有简单的算法可以解决这个问题。至于为您指明正确的方向，8x8 网格实际上只是图的一个特例，所以我将从图遍历算法开始。我发现在这种情况下，有时思考如何解决较小网格（例如 3x3 或 4x4）的问题，然后看看您的算法是否可以扩展到“完整尺寸”会有所帮助。

编辑：
我提出的算法是改进的深度优先遍历。要使用它，您必须将网格转换为图表。该图应该是无向的，因为连接的块在两个方向上均等连接。

每个图节点代表一个块，包含该块的值和一个 visited 变量。边权重代表其边对被跟随的抵抗力。通过对它们连接的节点的值求和来设置它们。根据您正在寻找的总和，您也许可以通过删除肯定会失败的边缘来优化这一点。例如，如果您要查找 15，则可以删除权重为 16 或更大的所有边。

算法的其余部分将执行与块数相同的次数，每个块作为起始块一次。通过跟随当前节点的最低权重边来遍历图，除非这会将您带到访问过的节点。将每个访问过的节点推入堆栈并将其 visited 变量设置为 true。为所遵循的每条路径保留一个运行总和。

• 每当达到所需的总和时，请将当前路径保存为答案之一。不要停止遍历，因为当前节点可能连接到零。
• 每当总数超过所需总和时，通过将 visited 设置为 false 并将当前节点从堆栈中弹出来回溯。
• 每当给定节点的所有边都被探索过时，就回溯。

在分析了从给定起始节点开始的每条可能路径后，就找到了包含该节点的每个答案。因此，删除所有接触起始节点的边并选择一个新的起始节点。

我还没有完全分析这个算法的效率/运行时间，但是......它不好。 （考虑在包含全零的图中要搜索的路径数量。）也就是说，它比纯粹的蛮力要好得多。