当迷宫是这样时用深搜老超时。怎么才能优化呢
....................
XXXXXXXXXXXXXXXXXXX.
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
..................XX
..................X.

X是墙
入口是 左上角 出口是右下角。迷宫不通

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

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


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

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

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

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

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

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