A*********3
发帖数: 70 | 1 请问判断一个迷宫有没有解，除了BFS, DFS,递归调用，还有什么别的办法吗？非常感
谢！ |
g*********s
发帖数: 1782 | 2 it depends on the problem. there's no general answer.
【在 A*********3 的大作中提到】
: 请问判断一个迷宫有没有解，除了BFS, DFS,递归调用，还有什么别的办法吗？非常感
: 谢！
|
A*********3
发帖数: 70 | 3 恩，就是最常见的那种迷宫，二维数组表示的，0表示路，1表示墙。
判断有没有解 |
g*********s
发帖数: 1782 | 4 please be more specific.
【在 A*********3 的大作中提到】
: 恩，就是最常见的那种迷宫，二维数组表示的，0表示路，1表示墙。
: 判断有没有解
|
a****n
发帖数: 1887 | |
A*********3
发帖数: 70 | 6 Give a maze, represented by an int array maze[][]
for example
0 1 0 0 0
1 1 1 0 0
1 0 1 1 1
0 0 0 0 1
1 1 1 1 1
0 is passage, 1 is wall
please give an algorithm to design if the maze is solvable or not |
g*********s
发帖数: 1782 | 7 construct a graph and solve shortest path b/w entry and exit.
【在 A*********3 的大作中提到】
: Give a maze, represented by an int array maze[][]
: for example
: 0 1 0 0 0
: 1 1 1 0 0
: 1 0 1 1 1
: 0 0 0 0 1
: 1 1 1 1 1
: 0 is passage, 1 is wall
: please give an algorithm to design if the maze is solvable or not
|
j*****u
发帖数: 1133 | 8 A* search
http://en.wikipedia.org/wiki/A*_search_algorithm
【在 A*********3 的大作中提到】
: 请问判断一个迷宫有没有解，除了BFS, DFS,递归调用，还有什么别的办法吗？非常感
: 谢！
|
r****o
发帖数: 1950 | 9 DP也可以吧。
【在 a****n 的大作中提到】
: BFS/DFS with mark table
|
h**6
发帖数: 4160 | 10 A*本质上还是Dijkstra
这题里面所有边长都为1，可以简化题目，不必使用优先队列，而用一个普通队列完成
遍历。
【在 j*****u 的大作中提到】
: A* search
: http://en.wikipedia.org/wiki/A*_search_algorithm
|
b*****e
发帖数: 474 | 11 如果只要判断有无解的话，用个 Disjoint Set 就够了。 |
