poj 3984 迷宫问题

#include<stdio.h>
#include<string.h>
#include<queue>
#define MAX 5000
using namespace std;
int map[5][5];
int n,m;
int bu[100][100];
int s[MAX];//记录位置的横坐标 
int s1[MAX];//记录位置的纵坐标 
struct node
{
	int x,y;
	int step;
	friend bool operator < (node a,node b)
	{
		return a.step>b.step;
	}
};
int bfs(int x1,int y1,int x2,int y2)
{
	int i,j,ok=0,k,t=1;
	int move[4][2]={0,1,0,-1,1,0,-1,0};
	priority_queue<node>q;
	node beg,end;
	beg.x=x1;
	beg.y=y1;
	q.push(beg);
	while(!q.empty())
	{
		end=q.top();
		q.pop();
		if(end.x==x2&&end.y==y2)
		{
			break;
		}
		for(i=0;i<4;i++)
		{
			beg.x=end.x+move[i][0];
			beg.y=end.y+move[i][1];
			if(0<=beg.x&&beg.x<5&&0<=beg.y&&beg.y<5&&map[beg.x][beg.y]==0)
			{
				map[beg.x][beg.y]=1;
				beg.step=end.step+1;
				bu[beg.x][beg.y]=beg.step;//记录对应步数时的节点位置 
				q.push(beg);
			}
		}
	}
	s[0]=4;s1[0]=4;//初值为终点，倒着打印出最短路径 
	for(i=end.step-1;i>=0;i--)
	{
		for(j=0;j<5;j++)
		{
			for(k=0;k<5;k++)
			{
				if(bu[j][k]==i)
				{
				    if((j==s[t-1]-1&&k==s1[t-1])||(k==s1[t-1]-1&&j==s[t-1]))//观察规律可知当前步的上一步必定是只能改变 
				    {                                                        //一个方向的值所以只有横坐标变或者只有纵坐标变 
				    	s[t]=j;  //记录下路径 
				    	s1[t]=k;
				    	t++;
				    }
				}
			}
		}
	}
	printf("(0, 0)\n");
	for(i=t-1;i>=0;i--)
	{
		printf("(%d, %d)\n",s[i],s1[i]);
	}
}
int main()
{
	int i,j,k,sum;
	for(i=0;i<5;i++)
	for(j=0;j<5;j++)
	scanf("%d",&map[i][j]);
	memset(bu,0,sizeof(bu));
	bfs(0,0,4,4);
	return 0;
}