A-Maze（week2 作业)

题目描述：

东东有一张地图，想通过地图找到妹纸。地图显示，0表示可以走，1表示不可以走，左上角是入口，右下角是妹纸，这两个位置保证为0。既然已经知道了地图，那么东东找到妹纸就不难了，请你编一个程序，写出东东找到妹纸的最短路线。

Input:
　　输入是一个5 × 5的二维数组，仅由0、1两数字组成，表示法阵地图。
Output:
　　输出若干行，表示从左上角到右下角的最短路径依次经过的坐标，格式如样例所示。数据保证有唯一解。
Sample Input:
0 1 0 0 0

0 1 0 1 0

0 1 0 1 0

0 0 0 1 0

0 1 0 1 0
Sample Output:
(0, 0)

(1, 0)

(2, 0)

(3, 0)

(3, 1)

(3, 2)

(2, 2)

(1, 2)

(0, 2)

(0, 3)

(0, 4)

(1, 4)

(2, 4)

(3, 4)

(4, 4)
Hint:
坐标(x, y)表示第x行第y列，行、列的编号从0开始，且以左上角为原点。
另外注意，输出中分隔坐标的逗号后面应当有一个空格。

解题思路：

本题是一道典型的bfs问题，从起点开始进行bfs搜索，直到终点结束。由题意可知，东东的下一步有四种可能，判断每一种可能是否可以压入队列中（在地图内，且无障碍物）。在搜索过程中，利用了一个二维矩阵dis[5][5]记录了当前走的步数，方便后续输出路线。
输出是通过递归实现的，输出终点前输出倒数第二个点的坐标，以此类推，直到递归到起点停止。

代码实现：

#include<iostream>
#include<queue>
using namespace std;
int m[10][10];
bool vis[5][5]={false};
int dis[5][5];
const int dx[]={0,0,1,-1};
const int dy[]={1,-1,0,0};
queue<pair<int,int> > s;
 
void bfs(int x,int y)
{
	s.push({x,y});
	vis[x][y]=true;
	dis[x][y]=1;
	while(!s.empty())
	{
		pair<int,int> point=s.front();
		s.pop();
		for(int w=0;w<4;w++)
		{
			int xx=point.first+dx[w];
			int yy=point.second+dy[w];
			if(xx>=0&&xx<5&&yy>=0&&yy<5&&!vis[xx][yy]&&m[xx][yy]!=1)
			{
				dis[xx][yy]=dis[point.first][point.second]+1;
				vis[xx][yy]=true;
				s.push({xx,yy}); 
			}	
		}
	}
}
void printff(int x,int y)
{
	if(x==0&&y==0)
	{
		cout<<"("<<x<<", "<<y<<")"<<endl;
		return;
	}
	for(int i=0;i<4;i++)
	{
		int xx=x+dx[i];
		int yy=y+dy[i];
		if(dis[xx][yy]+1==dis[x][y]&&m[xx][yy]==0&&xx>=0&&xx<5&&yy>=0&&yy<5)
			printff(xx,yy);
	}
	cout<<"("<<x<<", "<<y<<")"<<endl;
}
int main()
{	
	for(int i=0;i<5;i++)
		for(int j=0;j<5;j++)
			cin>>m[i][j];
	bfs(0,0);
	printff(4,4);
	return 0;
 }