迷宫问题求教怎么才能优化

#2

书生牛犊2016-09-23 22:41

你是不是忘了做标记，这个平面图算法复杂度也就O（M）;m取决于地图长宽。每一个结点只要踩过一次就可以了，下次不必递归了。
具体的代码实现就是你每到一个结点，先把他自身标记为used[][]=1;递归访问其右、上、下、左，但凡是跳出矩阵（x,y不合理的）或者已经标记为used[][]==1的就不走，没去的继续递归。任何时刻如果踩到了终点，结束递归。输出YES。如果所有可以被递归到的结点都用完了还是没踩到终点，输出NO。（注意，此时矩阵中还是可能有used==0的结点，形成原因就是那个地方被墙隔开了，根本就没路进去）

---------------想把这个迷宫走超时，那地图还得蛮大的呢！

#3

qq8266472352016-09-24 12:39

回复 2楼书生牛犊

标记完递归回溯一层不用撤标记吗

#4

书生牛犊2016-09-27 13:09

回复 3楼 qq826647235

不能撤标记，一旦扯了标记就会陷入无限循环。

这里的迷宫问题不是路径问题，是判断是否联通问题。

不是说要让你遍历出所有可行的路径方法。你只要证明能走到终点就行了。所以所有结点最多只要使用1次。

[此贴子已经被作者于2016-9-27 13:31编辑过]

迷宫问题求教 怎么才能优化