poj3984迷宫问题

#include<iostream>//广度优先算法 
using namespace std;
const int maxn=5;      //这里题目是5*5的地图 
int map[maxn][maxn];  //maxn*maxn大小的地图 
int dx[4]={1,-1,0,0};//可设置一个数组表示x方向上的变化 
int dy[4]={0,0,-1,1}; //可设置一个数组表示y方向上的变化
int front=0,rear=1;
struct node{
	int x,y,pre;//x,y为坐标，pre用来表示前一个元素的下标（即保存路径） 
}q[100]; 

void print(int i)
{
	if(q[i].pre!=-1)
	{
		print(q[i].pre);
		cout<<"("<<q[i].x<<","<<q[i].y<<")"<<endl;
		
	}
 } 
void bfs(int x1,int y1)
{
	q[front].x=x1;
	q[front].y=y1;
	q[front].pre=-1;
	while(front<rear)  //当队列不空 
	{
		for(int i=0;i<4;i++)
		{
			int a=dx[i]+q[front].x;//位置 
			int b=dy[i]+q[front].y;
			if(a<0||a>=maxn||b<0||b>=maxn||map[a][b])//是否在迷宫内，是否可行  若map[a][b]=1,则说明该路不可行（1为墙）跳过这个，进行下一循环 
			continue;
			else
			{
				map[a][b]=1;
				q[rear].x=a;
				q[rear].y=b;
				q[rear].pre=front;
				rear++;//入队 
			 } 
			 if(a==(maxn-1)&&b==(maxn-1))
			 print(front);
		 } 
		 front++;
	}
 } 
 int main()
 {
 	int i,j;
 	for(i=0;i<maxn;i++)  //定义一个5*5的二维数组（迷宫） 
 	for(j=0;j<maxn;j++)
 	cin>>map[i][j];
 	cout<<"(0,0)"<<endl; //起点 
 	bfs(0,0);
 	cout<<"("<<maxn<<","<<maxn<<")"<<endl;  //终点 
 	return 0;
 }

输入输出：

解题思路：