POJ 3984：迷宫问题 bfs+递归输出路径

迷宫问题

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 11844		Accepted: 7094

Description

定义一个二维数组：

int maze[5][5] = {

	0, 1, 0, 0, 0,

	0, 1, 0, 1, 0,

	0, 0, 0, 0, 0,

	0, 1, 1, 1, 0,

	0, 0, 0, 1, 0,

};

它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。

Input

一个5 × 5的二维数组，表示一个迷宫。数据保证有唯一解。

Output

左上角到右下角的最短路径，格式如样例所示。

Sample Input

Sample Output

(0, 0)
(1, 0)
(2, 0)
(2, 1)
(2, 2)
(2, 3)
(2, 4)
(3, 4)
(4, 4)

bfs+记录之前的路径，输出时递归输出就可以了。

代码：

#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <queue>
#pragma warning(disable:4996)
using namespace std;

int value[7][7];
int pre[7][7];
int flag[7][7];

void bfs()
{
	memset(flag,0,sizeof(flag));
	memset(pre,-1,sizeof(pre));

	queue<int>x;
	queue<int>y;

	while(x.size())x.pop();
	while(y.size())y.pop();

	x.push(0);
	y.push(0);

	int a;
	int b;
	while(x.size())
	{
		a=x.front();
		b=y.front();

		x.pop();
		y.pop();

		flag[a][b]=1;

		if(a>0&&flag[a-1][b]==0&&value[a-1][b]==0)
		{
			pre[a-1][b]=a*10+b;
			x.push(a-1);
			y.push(b);
		}
		if(b<4&&flag[a][b+1]==0&&value[a][b+1]==0)
		{
			pre[a][b+1]=a*10+b;
			x.push(a);
			y.push(b+1);
		}
		if(b>0&&flag[a][b-1]==0&&value[a][b-1]==0)
		{
			pre[a][b-1]=a*10+b;
			x.push(a);
			y.push(b-1);
		}
		if(a<4&&flag[a+1][b]==0&&value[a+1][b]==0)
		{
			pre[a+1][b]=a*10+b;
			x.push(a+1);
			y.push(b);
		}
	}

}

void prin(int x,int y)
{
	if(pre[x][y]!=-1)
	{
		int y_pr=pre[x][y]%10;
		int x_pr=pre[x][y]/10;
		prin(x_pr,y_pr);
	}
	cout<<"("<<x<<", "<<y<<")"<<endl;
}

int main()
{
	int i,j;
	for(i=0;i<=4;i++)
	{
		for(j=0;j<=4;j++)
		{
			cin>>value[i][j];
		}
	}
	
	bfs();
	prin(4,4);

	return 0;
}