【题目描述】
定义一个二维数组:
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表示可以走的路,只能横着走或竖着走,不能斜着走,要求编程序找出从左上角到右下角的最短路线。
【输入】
一个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
【输出样例】
(0, 0)
(1, 0)
(2, 0)
(2, 1)
(2, 2)
(2, 3)
(2, 4)
(3, 4)
(4, 4)
【思路】:
进行bfs并用一个二维数组记录一下每一个点的下一个点是哪个,当找到目标点时用递归的方法一步一步输出路径,弯事大吉~
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<string> #include<cstdlib> #include<queue> #include<vector> using namespace std; ; ; char a[N][N]; bool vis[N][N]; ][]={{-,},{,},{,-},{,}}; struct node { int x; int y; }q[],res[N][N]; void print(int x,int y) { &&y==-) return; print(res[x][y].x,res[x][y].y); printf("(%d, %d)\n",x,y); } void bfs(int sx,int sy,int ex,int ey) { ,tail=; memset(vis,,sizeof(vis)); vis[sx][sy]=; res[sx][sy].x=-; res[sx][sy].y=-; q[tail].x=sx; q[tail].y=sy; tail++; while(head<tail) { int x=q[head].x; int y=q[head].y; if(x==ex&&y==ey) { print(x,y); break; } ;i<;i++) { ]; ]; &&nx<n&&ny>=&&ny<n&&vis[nx][ny]==&&a[nx][ny]==) { vis[nx][ny]=; q[tail].x=nx; q[tail].y=ny; tail++; res[nx][ny].x=x; res[nx][ny].y=y; } } head++; } } int main() { ;i<n;i++) ;j<n;j++) scanf("%d",&a[i][j]); bfs(,,n-,n-); ; }