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) |
思路：
广搜 。 通过path[i][j] 记录上一个点是通过 road[i][] 到达本点，通过 path[i][j] 回推经过的路径。
参考代码：
#include <iostream>
#include <cstring>
#include <queue>
#include <cstdio>
using namespace std;
typedef struct point
{
int x, y;
} P;
const int N = 5;
// m 存储迷宫
int m[N][N], road[4][2]= {0,-1,0,1,-1,0,1,0}, vis[N][N];
// 通过path[i][j] 记录上一个点是通过 road[i][] 到达本点
// 通过 path[i][j] 回推经过的路径
int path[N][N];
queue <P> Q;
void bfs(P now)
{
Q.push(now);
vis[now.x][now.y] = 1;
while(!Q.empty())
{
now =Q.front();
Q.pop();
if(now.x==4 && now.y== 4)
return ;
for(int i=0; i<4; i++)
{
P tem;
tem.x = now.x + road[i][0], tem.y = now.y + road[i][1];
if((tem.x>=0&&tem.x<N&&tem.y>=0&&tem.y<N) && vis[tem.x][tem.y] == 0 && m[tem.x][tem.y] == 0)
{
Q.push(tem);
path[tem.x][tem.y]= i;
vis[tem.x][tem.y] = 1;
}
}
}
}
int main()
{
int i, j;
// 输入迷宫
for(i=0; i<N; i++)
for(j=0; j<N; j++)
scanf("%d",&m[i][j]);
P now;
now.x = 0, now.y = 0;
// 初始化
memset(vis, 0, sizeof(vis));
memset(path, 0, sizeof(path));
bfs(now);
now.x = 4, now.y = 4;
int k = 0;
P step[100];
while(1)
{
step[++k] = now;
if(now.x == 0 && now.y == 0)
break;
int temp = path[now.x][now.y];
now.x -= road[temp][0];
now.y -= road[temp][1];
}
for(int i=k; i>=1; i--)
{
printf("(%d, %d)\n",step[i].x,step[i].y);
}
return 0;
}