寻找一个模式来搜索网格上的特定路径有简单节点的二维网格,如:
public class TileNode {
private final int ID;
public TileNode leftNeightbour;
public TileNode topNeightbour;
public TileNode rightNeightbour;
public TileNode bottomNeightbour;
private TileState currentTileGameState;
}
如果其中一个邻居无法通过当前节点,则其状态设置为
outOfGame
。我已经尝试过递归DFS ALG来寻找所有的路径,但是复杂性是可怕的。我将尝试使用以下搜索路径剪切搜索集合:红色的节点是我们开始和结束的地方,黑色的线是应该穿过其他节点(邻居)的路径,这些节点是可以通过的。
我们不考虑除指定路径以外的任何其他路径当然,这些路径的长度是没有限制的。
编辑:
我想检查两个节点之间是否存在任何沿着图像路径的路径。可能很简单。可能不止一个。它看起来与那些路径相似example
最佳答案
我认为你的数据结构并不适合寻找你想要的路径,因为你不是在寻找任何路径,而是寻找某种形状的路径。
使用真实的数据网格(即二维数组)可能更好,而不是具有链接的类似于图形的结构。至少你应该知道你的水平和垂直位置(x,y)。
然后你可以这样处理你的问题:找到垂直路径,即中间部分垂直的路径。当两个平铺的y坐标(向上)相同时,没有垂直路径。那就找一条平坦的路。只有两段或三段的路径可视为三段路径的退化情形。
因此,如果瓷砖的y位置不同:
找到最左边和最右边的位置,该位置可以从开始和结束平铺[l1,r1]和[l2,r2]到达。
当L1和L2都超出网格的左边界,或者R1和R2都超出网格的右边界时,就有了一条路径。
找到两个范围的交集,[l,r]=[l1,r1][l2,r2]。如果交叉点为空,则没有(垂直)路径。
对于[l,r]中的所有x位置,测试(x,y1)到(x,y2)是否有可能的直线。
如果没有垂直路径,则对水平路径执行相同的操作。