接工程网站北京猎梦网站建设

标签：宽度优先搜索
题意：给定$n$x$m$由$\#$（墙）、$.$（空地）组成的地图，求从左上角到右下角的最少步数，每次只允许上下左右移动一格，不允许走出地图和走到$\#$（墙）上。
题解：BFS 模板题，判断下一个能否走的点，经典三要素：

1. 下个点是否是障碍物（宽泛来说是题目中的限制条件）
2. 下个点是否走过（避免死循环）
3. 下个点是否在地图内

代码：

#include <bits/stdc++.h>
using namespace std;int n, m;
int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};char a[1005][1005];
bool vis[1005][1005];
struct node {int x, y, step;
};void bfs() {queue <node> q;vis[1][1] = 1;q.push({1, 1, 0});while (!q.empty()) {node u = q.front();q.pop();if (u.x == n && u.y == m) {cout << u.step << endl;return ;}for (int i = 0; i < 4; i++) {int nx = u.x + dx[i];int ny = u.y + dy[i];if (nx < 1 || nx > n || ny < 1 || ny > m) continue;if (vis[nx][ny] || a[nx][ny] == '#') continue;vis[nx][ny] = 1;q.push({nx, ny, u.step + 1});}}cout << "No solution" << endl;
}int main() {cin >> n >> m;for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)cin >> a[i][j];bfs();return 0;
}