POJ 3984 迷宫问题 广搜迷宫解法

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

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

Sample Output

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

本题是经典的迷宫搜索问题了，使用广搜比使用深搜效率要高。

思路关键点：

1 从终点出发查找起点，这样方便记录路径

2 每次查找到下一个空格，可走方格之后，能够立即标识该格为不可走了

3 找到起点之后，立即能够返回

关键是第二点为什么会成立？

由于我们须要找最短路径，仅仅要最先能够达到，那么就肯定是最短路径，不须要从其它方向进入了。

#include <stdio.h>
#include <string.h>
#include <limits.h>
#include <queue>
#include <algorithm>
#include <xutility>
using namespace std;

const int N = 5;
int Maze[N][N];
pair<int, int> path[N][N];
const int BLOCK = 1;
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};

inline bool isLegal(int x, int y)
{
	return x>=0 && y>=0 && x<N && y<N && !Maze[x][y];
}

template<typename T>
inline bool equ(T t1, T t2) { return t1 == t2; }

void bfsGetPath(int sx = 0, int sy = 0, int ex = 4, int ey = 4)
{
	queue<pair<int, int> > qu;
	qu.push(make_pair(ex, ey));//初始条件，从终点開始搜索到起点。方便记录路径
	path[ex][ey] = make_pair(-1, -1);//记录终点结束条件值
	Maze[ex][ey] = BLOCK;//标志为不可走

	while (!qu.empty())
	{
		pair<int, int> fa = qu.front();	qu.pop();
		for (int i = 0; i < 4; i++)
		{
			int nx = dx[i] + fa.first, ny = dy[i] + fa.second;
			if (!isLegal(nx, ny)) continue;//跳过不可走的方格

			path[nx][ny] = fa;//记录路径
			if (equ(nx, sx) && equ(ny, sy)) return;//找到起点能够返回

			qu.push(make_pair(nx, ny));//入队列
			Maze[nx][ny] = BLOCK;//入队列的方格，能够立即置为不可走状态
		}
	}
}

int main()
{
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			scanf("%d", Maze[i]+j);
		}
	}

	bfsGetPath();

	int x = 0, y = 0;//起点開始输出路径点
	while (x != -1)
	{
		printf("(%d, %d)\n", x, y);
		int nx = path[x][y].first;
		int ny = path[x][y].second;
		x = nx, y = ny;//注意须要使用中间变量nx， ny
	}
	return 0;
}