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 Input：
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
Sample Output：
(0, 0)
(1, 0)
(2, 0)
(2, 1)
(2, 2)
(2, 3)
(2, 4)
(3, 4)
(4, 4)
程序代码：
#include<stdio.h> #include<string.h> struct node { int x,y,pre; }q[50]; int head=0,tail=0; int a[5][5],vis[5][5]; int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}}; void bfs(int x1,int y1,int x2,int y2) { q[0].x=x1; q[0].y=y1; q[0].pre=-1; tail++;//队尾向后移动 vis[x1][y1]=1;//标记 while(head<tail) { for(int i=0;i<4;i++) { int tx=q[head].x+dir[i][0]; int ty=q[head].y+dir[i][1]; if(tx<0||tx>=5||ty<0||ty>=5||vis[tx][ty]==1||a[tx][ty]==1) continue;//出界，或者这个点已经走过，或者这个点是障碍 q[tail].x=tx; q[tail].y=ty; q[tail].pre=head; tail++; vis[tx][ty]=1; if(tx==x2&&ty==y2)//走到迷宫出口 return ; } head++; } } void print(node now) { if(now.pre==-1) printf("(%d, %d)\n",now.x,now.y); else { print(q[now.pre]); printf("(%d, %d)\n",now.x,now.y); } } int main() { for(int i=0;i<5;i++) for(int j=0;j<5;j++) scanf("%d",&a[i][j]); bfs(0,0,4,4);//带入起点和终点坐标 print(q[tail-1]);//将队列中的元素依次输出 return 0; }
