题解 | #迷宫问题#参考了别人的

/*定义一个二维数组 N*M ，如 5 × 5 数组下所示：
int maze[5][5] = {
0, 1, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 1, 0,
};
它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，
只能横着走或竖着走，不能斜着走，要求编程序找出从左上
角到右下角的路线。入口点为[0,0],既第一格是可以走的路。
*/
#include <iostream>
#include <queue>
#include <stack>
using namespace std;
typedef struct pos
{
	int x;
	int y;
}pos;
pos father[10][10];
void BFS(int a[][10],int n,int m,pos p)//二维数组做形参第二维或更高维的大小不可以省略 
{
	int visited[10][10]={0};
	pos v;
	pos W,A,S,D;
	queue<pos>q;
	q.push(p);
	visited[p.x][p.y]=2;	
	while(!q.empty())
	{
		v=q.front();		
		W.x=v.x-1;  W.y=v.y;//上 
		A.x=v.x;  A.y=v.y-1;//左 
		S.x=v.x+1;  S.y=v.y;//下 
		D.x=v.x;  D.y=v.y+1;//右 
		q.pop();
			if(W.x>=0&&W.x<n&&W.y>=0&&W.y<m&&a[W.x][W.y]==0&&visited[W.x][W.y]==0) 
			{				
				visited[W.x][W.y]=2;
				q.push(W);
				father[W.x][W.y]={v.x,v.y};
				if(W.x==n-1&&W.y==m-1) break;
			}
			if(A.x>=0&&A.x<n&&A.y>=0&&A.y<m&&a[A.x][A.y]==0&&visited[A.x][A.y]==0)
			{
				visited[A.x][A.y]=2;
				q.push(A);
				father[A.x][A.y]={v.x,v.y};
				if(A.x==n-1&&A.y==m-1) break;
			}
			if(S.x>=0&&S.x<n&&S.y>=0&&S.y<m&&a[S.x][S.y]==0&&visited[S.x][S.y]==0)
			{				
				visited[S.x][S.y]=2;
				q.push(S);
				father[S.x][S.y]={v.x,v.y};
				if(S.x==n-1&&S.y==m-1) break;
			} 
			if(D.x>=0&&D.x<n&&D.y>=0&&D.y<m&&a[D.x][D.y]==0&&visited[D.x][D.y]==0)
			{				
				visited[D.x][D.y]=2;
				q.push(D);
				father[D.x][D.y]={v.x,v.y};
				if(D.x==n-1&&D.y==m-1) break;
			} 
	}
//	for(int i=0;i<n;i++)
//	{
//		for(int j=0;j<m;j++)
//		{
//			cout<<"f:"<<father[i][j].x<<","<<father[i][j].y<<" ";
//		}
//		cout<<endl;
//	}	
	
} 
void dfs(pos p)
{
	pos q;	
	if(p.x==0&&p.y==0) return;
	q=father[p.x][p.y];
	dfs(q);
	cout<<"("<<p.x<<","<<p.y<<")"<<endl;	
}
int main()
{
	int a[10][10];	
	int n,m;
	cin>>n>>m;
	pos p={0,0};

	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			cin>>a[i][j];
		}
	}
//	cout<<"bfs:"<<endl;
	BFS(a,n,m,p);
	pos t={n-1,m-1};
	cout<<"(0,0)"<<endl;
	dfs(t);
}