迷宫问题: 广度优先搜索

问题描述

东东有一张地图，想通过地图找到妹纸。地图显示，0表示可以走，1表示不可以走，左上角是入口，右下角是妹纸，这两个位置保证为0。既然已经知道了地图，那么东东找到妹纸就不难了，请你编一个程序，写出东东找到妹纸的最短路线。

Input

输入是一个5 × 5的二维数组，仅由0、1两数字组成，表示法阵地图。

Output

输出若干行，表示从左上角到右下角的最短路径依次经过的坐标，格式如样例所示。数据保证有唯一解。

Sample

input: 
0 1 0 0 0
0 1 0 1 0
0 1 0 1 0
0 0 0 1 0
0 1 0 1 0

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

解题思路

广度优先搜索(BFS)：
从起始点开始遍历，先从相邻的点找起，如果可行，则加入生成的路径，同时已经加入的点不会再次访问。比如题中样例，BFS生成的路径用2表示，则：

0 1 0 0 0				2 1 2 2 2
0 1 0 1 0				2 1 2 1 2
0 1 0 1 0		→		2 1 2 1 2
0 0 0 1 0				2 2 2 1 2
0 1 0 1 0				0 1 2 1 2

再比如：

0 1 0 0 0				2 1 2 2 2
0 1 0 1 0				2 1 2 1 2
0 0 0 1 0		→		2 2 2 1 2
0 1 0 1 1				0 1 2 1 1
0 1 0 0 0				0 1 2 2 2

同时这也产生了一个问题：没必要走的点加入了路径中！广搜产生的分支好比一棵树的枝干的枝杈，主枝一直往前延申直到终点，但分支也随之产生去探寻分支的终点，直到某个枝杈到达了目标终点，才能分辨出谁是主枝，剩下的才是分支。

所以通过终点，往回退，避开产生的分支，最后走回起点，这样就生成了最终路径。

详见代码。

源代码

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

/*点的结构体  表示(x, y)坐标*/
struct point {
	int x, y;
	int dis;//用于记录原点到当前点路径上的距离
};

/*用于上下左右移动*/
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };

int reach[5][5];//标记到达的数组

vector<point> path;//生成路径

bool neighbour(point a, point b) {//判断两点是否相邻(上、下、左、右)
	return (abs(a.x - b.x) == 1 && a.y == b.y) || (abs(a.y - b.y) == 1 && a.x == b.x);
}

void bfs(int maze[5][5]) {
    //初始化点坐标
	point dot;
	dot.x = 0;
	dot.y = 0;
	dot.dis = 0;
	queue<point> q;//队列 用于记录走过的点与下一可行点 保证先进先出
	q.push(dot);//起点(0, 0)开始，入队
	reach[0][0] = 1;//(0, 0)已走过

	while (!q.empty()) {
		point curr = q.front();//从队首取点，保证先进先出
		path.push_back(curr);//点可行 记入生成路径
		q.pop();//取走后就要出队
		for (int i = 0; i < 4; i++) {//从取走的点开始上下左右判断可不可以走
			int x = curr.x + dx[i];
			int y = curr.y + dy[i];
			/*若在图边界内 且 非墙 且 还没走*/
			if (x >= 0 && x < 5 && y >= 0 && y < 5
				&& maze[x][y] != 1 && reach[x][y] != 1) {
				reach[x][y] = 1;//reached
				curr.x = x, curr.y = y;
				curr.dis++;
				q.push(curr);//可行 入队
			}
		}
	}
}

int main() {
	int maze[5][5];
	for (int i = 0; i < 5; i++)
		for (int j = 0; j < 5; j++)
			cin >> maze[i][j];//录入迷宫

	for (int i = 0; i < 5; i++)
		for (int j = 0; j < 5; j++)
			reach[i][j] = 0;//初始化所有点未到达

	bfs(maze);//生成路径

	int end;
	for (int i = 0; i != path.size(); ++i)//从生成路径中寻找终点的位置
		if (path.at(i).x == 4 && path.at(i).y == 4)
			end = i;//是终点

	if (end != path.size() - 1)//如果终点不是生成路径的最后一个点的话
		path.erase(path.begin() + end + 1, path.end());//后面的分支就可以移除了
	
    /*从终点开始往前找路径*/
	for (int i = path.size() - 1; i > 0; i--) {
		if (!neighbour(path.at(i), path.at(i - 1)) ||
			(path.at(i).dis - path.at(i - 1).dis != 1))
         /* 若前后的点非相邻点 或相邻两点距原点的路径距离差非1 */
			path.erase(path.begin() + i - 1);//这个点可删除
	}

	for (int i = 0; i != path.size(); ++i)//输出
		cout << "(" << path.at(i).x << ", " << path.at(i).y << ")" << endl;

	return 0;
}