欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-05-20 22:52:09
...

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;
}