POJ 3984 迷宫问题 (Dijkstra)
迷宫问题
Description定义一个二维数组： int maze[5][5] = {0, 1, 0, 0, 0,0, 1, 0, 1, 0,0, 0, 0, 0, 0,0, 1, 1, 1, 0,0, 0, 0, 1, 0,};它表示一个迷宫，其中的1表示墙壁，虚拟主机，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。
Input一个5 × 5的二维数组，表示一个迷宫。数据保证有唯一解。
Output左上角到右下角的最短路径，格式如样例所示。
Sample Input0 1 0 0 00 1 0 1 00 0 0 0 00 1 1 1 00 0 0 1 0
Sample Output(0, 0)(1, 0)(2, 0)(2, 1)(2, 2)(2, 3)(2, 4)(3, 4)(4, 4)
解决方案：
对于这题，我们可以把它maze数组转化为一个图，不能通过的话，即两点之间无路径，然后利用Dijkstra算法寻找S点到T点的最短路径。
Dijkstra算法可参考维基百科迪科斯彻算法，美国空间，其核心代码如下：
1 function Dijkstra(G, w, s)d[v] := infinityprevious[v] := undefinedd[s] := S := empty set 7Q := set of all verticesu := Extract_Min(Q)10 S.append(u)11for each edge outgoing from u as (u,v)d[v] := d[u] + w(u,v)previous[v] := u// 记录前趋顶点
对于上图，我们的算法可以大大简化，香港虚拟主机，因为每条路径的权重都相等，由于Dijkstra是按照广度优先搜索来进行遍历的，因而在我们这，先到达这个点的路径即为最短路径(这里对照上图，在纸上画一画就可以体会到)。
对于第9行的u := Extract_Min(Q) ，我们就用一个队列来表示Q，因为先进来的点的距离不会大于后进来的点，每次从队列头部取出元素，效果与Extract_Min(Q)一样。
代码如下：
POJ 3984
1 #include <stdio.h> 2 #include <string.h>N 5print(int value, int prev[N*N]) 7 { 8if (value >= 0) 9 {10int x = value/N;11int y = value%N;12 print(prev[value], prev);, x, y);14 }15 }solve(int maze[N][N])18 {memset(visited, offset[N-1][2] = {{-{{ };queue[N*N];front = rear = x = y = queue[++rear] = visited[x][y] = prev[N*N];memset(prev, -prev[(front <= rear)43 {44int i;45int newx;46int newy;x = queue[front]/N;49y = queue[front]%N;(i = 0; i < N – 1; i++)52 {newy = y + offset[i][(newx >= 0 && newx < N && newy >= 0 && newy < N && !visited[newx][newy] && !maze[newx][newy])56 {57rear = (rear + 1)%(N*N);58queue[rear] = newx*N + newy;59prev[newx*N + newy] = x*N + y;60visited[newx][newy] = 1;61 }62 }63 }64print(N*N – 1, prev);65 } main()68 {69int maze[N][N];70int i = 0;71int j = 0;, &maze[i][j++]) != EOF)73 {74if (j == 5)75 {76i++;77j = 0;78 }79if (i == 5)80 {81 solve(maze);82i = 0;83 }84 };86 }
posted on
悠然享受和大自然融合之乐。
