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 就够了。 |