第四篇,BFS搜索---------巧解迷宫问题

发布于:2022-12-13 ⋅ 阅读:(264) ⋅ 点赞:(0)

想法来自:https://www.acwing.com/solution/content/2078/

一、题目

 


二、解题思路

1、走迷宫问题常见思路之一: BFS搜索

2、从左上走到右下:需要一步步走,设置距离数组,由于会有多条路径,每一个坐标都对应其从

源点走到那里的距离。因此要设置成数组。

3、很多人会问为什么还要选择bfs,我觉得:迷宫肯定有很多分岔口,如果要深度搜索,一个一个

方向来查看,直到不能走再回溯,那样时间复杂度想想都会很高。

但如果使用了bfs,很多路口可以齐头并进,没有走到终点但是不能动的直接撤出bfs中(涉及队列

思想)。

4、涉及上下左右走的问题时候,需要设置两个数组dx,dy,例如向左走,就是横坐标-1,纵坐标

不变。

5、那么怎么处理走到头但没有走到终点的点呢?------队列。

走到头的点,肯定上下左右都没法走了,这时候让他退出队列,不用回溯什么的了,毕竟之前的路

都走过,回溯很麻烦。

三、代码实现


const int N = 120;
int map[N][N];
int dis[N][N];

typedef pair<int, int> P;

void bfs(int m ,int n) {
	queue<P>q1;
	q1.push({0, 0});
	dis[0][0] = 0;
	int dx[4] = { 0, 1, 0, -1 };
	int dy[4] = { 1, 0, -1, 0 };
	while (!q1.empty()) {
		P p1 = q1.front();
		q1.pop(); // 走过哪些点,直接清除出去队列,目的以后当走到头的时候,可以直接清除出去。
		for (int i = 0; i < 4; i++) {
			int x = p1.first + dx[i], y = p1.second + dy[i];
			if (x >= 0 and x < m and y >= 0 and y < n and
				!map[x][y] && map[x][y] != -1) {
				q1.push({ x, y });
				dis[x][y] = dis[p1.first][p1.second] + 1;
				map[x][y] = -1;   // 走过的点设置成-1.
			}

		}
	}
	cout << dis[m - 1][n - 1];
}

int main() {
	int m, n;
	cin >> m >> n;
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++)
			cin >> map[i][j];  // 创建墙壁以及可走的点。
		cout << endl;
	}
	for (int i = 0; i < m; i++)
		for (int j = 0; j < n; j++)
			dis[i][j] = 0;  // 将每个点对应的距离全部设置成1.
	bfs(m ,n);

}


网站公告

今日签到

点亮在社区的每一天
去签到