java - 如何有效地找到特定的路径模式？

Question

寻找一种模式来搜索网格上的特定路径。有简单节点的二维网格，如:

public class TileNode {
    private final int ID;

    public TileNode leftNeightbour;
    public TileNode topNeightbour;
    public TileNode rightNeightbour;
    public TileNode bottomNeightbour;
    private TileState currentTileGameState;
}

如果其中一个邻居无法通过当前节点，则它的状态设置为 outOfGame。我已经尝试使用递归 DFS 算法来查找所有路径，但复杂性非常高。我将尝试使用这些搜索路径来削减搜索集合:

红色节点是我们开始和结束的地方，黑线是应该经过其他节点(邻居)的路径，这些节点可以通过。

我们不考虑指定路径以外的任何其他路径。当然，这些路径的长度没有限制。

编辑: 我想检查两个节点之间是否存在任何遵循图像路径的路径。这可能很简单。可能存在不止一个。它看起来与那些路径相似 example

Answer 1

我认为你的数据结构不适合自己寻找你想要的那种路径，因为你不是在寻找任何路径，而是在寻找某种形状的路径。

使用真正的数据网格可能更好，即二维数组，而不是带有链接的类似图形的结构。至少你应该知道你的水平和垂直位置 (x, y)。

然后你可以这样处理你的问题:找到垂直路径，即中间部分是垂直的路径。当两个图 block 的 y 坐标(向上)相同时，没有垂直路径。然后找到水平路径。只有两段或三段的路径可以被认为是三段路径的退化情况。

所以如果 tiles 的 y 位置不同:

• 找到从开始和结束图 block [L1, R1] 和 [L2, R2] 可以到达的最左边和最右边的位置。
• 当 L1 和 L2 都超出了网格的左边界，或者如果 R1 和 R2 都超出了网格的右边界，那么您就有了路径。
• 找到两个范围的交集，[L, R] = [L1, R1] ∩ [L2, R2]。如果那个交叉点是空的，则没有(垂直)路径。
• 对于 [L, R] 中的所有 x 位置，测试是否存在从 (x, y1) 到 (x, y2) 的直线。

如果没有垂直路径，则对水平路径执行相同的操作。