想法来自: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);
}