POJ3984 迷宫问题 BFS

看题传送门：http://poj.org/problem?id=3984

BFS水一发

明天帮学弟挑电脑顺便去玩。接下来几天好好看数据结构。嗯哼。

这题标准的BFS应用，唯一需要注意的是需要输出中间的过程，要记录。（递归输出答案）

#include<iostream>

#include<cstring>

#include<queue>

using namespace std;

int maze[5][5];

bool vis[5][5];

const int dx[]={1,0,0,-1};

const int dy[]={0,1,-1,0};

struct site

{

	int x,y;

	int px,py;

	site(int i,int j):x(i),y(j){}

	site(){}

}a[10][10];

queue<site> q;

void print_ans(int x,int y)

{

    if(a[x][y].px!=-1&&a[x][y].py!=-1)

        print_ans(a[x][y].px,a[x][y].py);

    printf("(%d, %d)\n",x,y);

}

void bfs()

{

	memset(vis,0,sizeof(vis));

	vis[0][0]=true;

	a[0][0].px=-1;

	a[0][0].py=-1;

	q.push(site(0,0));

	while(!q.empty())

	{

		site temp=q.front();

		q.pop();

		int x=temp.x,y=temp.y;

		for(int i=0;i<4;i++)

		{

			int nex=x+dx[i];

            int ney=y+dy[i];

			if(nex>=0&&nex<5&&ney>=0&&ney<5 && vis[nex][ney]==false && maze[nex][ney]==0)

			{

				a[nex][ney].px=x;

				a[nex][ney].py=y;

				if(nex==4&&ney==4) return;

				q.push(site(nex,ney));

				vis[nex][ney]=true;

			}

		}

	}

}

int main()

{

	for(int i=0;i<5;i++)

		for(int j=0;j<5;j++)

			cin>>maze[i][j];

	bfs();

	print_ans(4,4);

}