1255：迷宫问题 2021-01-09

1255：迷宫问题
时间限制: 1000 ms         内存限制: 65536 KB
【题目描述】
定义一个二维数组：
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)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int map[6][6],p[50][4],m[50];
int xx[4]={-1,1,0,0};
int yy[4]={0,0,-1,1};
int x,y,t=0,w=1;
void bfs(int a,int b){
	map[a][b]=1;
	p[1][1]=a,p[1][2]=b,p[1][3]=0;
	while(w>t){
		t++;
		for(int i=0;i<4;i++){
			x=p[t][1]+xx[i];
			y=p[t][2]+yy[i];
			if(x>=0&&x<5&&y>=0&&y<5&&map[x][y]==0){
				w++;p[w][1]=x;p[w][2]=y;
				p[w][3]=t;map[x][y]=1;
				if(x==4&&y==4)return;
			}	
		}
	}
}
int main(int argc, char *argv[])
{
	for(int i=0;i<5;i++)
		for(int j=0;j<5;j++)
			scanf("%d",&map[i][j]);
	bfs(0,0);
	int k=0;
	while(w>=1){
		k++;m[k]=w;w=p[w][3];
	}
	for(int i=k;i>=1;i--)
		printf("(%d, %d)\n",p[m[i]][1],p[m[i]][2]);
	return 0;
}