BFS入门经典

#include cstring #include iostream #include algorithm #include queue using namespace std; // pairint,int 用来存一个点的坐标 (x, y) typedef pairint, int PII; const int N 110; int n, m; // n 行 m 列 int g[N][N], d[N][N]; // g存地图d存每个点到起点的距离 // bfs 求从 (0,0) 到 (n-1,m-1) 的最短路 int bfs() { queuePII q; // 队列BFS 的核心数据结构先进先出 // 先把距离数组全部初始化为 -1 // -1 表示这个点还没有被访问过 memset(d, -1, sizeof d); // 起点距离自己为 0 d[0][0] 0; // 把起点放入队列 q.push({0, 0}); // 四个方向上、右、下、左 int dx[4] {-1, 0, 1, 0}, dy[4] {0, 1, 0, -1}; // 只要队列不空就一直扩展 while (q.size()) { // 取出队头元素 auto t q.front(); q.pop(); // 枚举当前点的四个方向 for (int i 0; i 4; i ) { // 新坐标 int x t.first dx[i], y t.second dy[i]; // 判断这个点能不能走 // 1. 没越界 // 2. 这个位置不是墙g[x][y] 0 表示能走 // 3. 这个点之前没被访问过d[x][y] -1 if (x 0 x n y 0 y m g[x][y] 0 d[x][y] -1) { // 因为是从当前点走一步过来的 // 所以新点的距离 当前点距离 1 d[x][y] d[t.first][t.second] 1; // 把新点加入队列后面继续从它往外扩展 q.push({x, y}); } } } // 返回终点的距离 // 如果终点没被访问到那么这里就是 -1 return d[n - 1][m - 1]; } int main() { // 输入迷宫的行数和列数 cin n m; // 输入地图 // 0 表示可以走 // 1 表示障碍物不能走 for (int i 0; i n; i ) for (int j 0; j m; j ) cin g[i][j]; // 输出从左上角到右下角的最短路长度 cout bfs() endl; return 0; }这题为什么用 BFS因为每走一步代价都一样都是1所以这是一个无权图最短路最适合用 BFS。d[x][y]表示什么表示从起点(0,0)走到(x,y)的最少步数为什么d初始化成-1因为要表示“这个点还没走到过”。为什么 BFS 能保证最短路因为 BFS 是一层一层往外扩展的先到的都是距离 1 的点再到距离 2 的点再到距离 3 的点所以某个点第一次被访问到时一定就是最短距离。别的写法2. 用struct存坐标有些人不喜欢pair.first / pair.second会觉得不直观就会写成结构体。#include iostream #include cstring #include queue using namespace std; const int N 110; int n, m; int g[N][N], d[N][N]; struct Node { int x, y; }; int bfs() { queueNode q; memset(d, -1, sizeof d); q.push({0, 0}); d[0][0] 0; int dx[4] {-1, 0, 1, 0}; int dy[4] {0, 1, 0, -1}; while (!q.empty()) { Node t q.front(); q.pop(); for (int i 0; i 4; i) { int x t.x dx[i]; int y t.y dy[i]; if (x 0 x n y 0 y m g[x][y] 0 d[x][y] -1) { d[x][y] d[t.x][t.y] 1; q.push({x, y}); } } } return d[n - 1][m - 1]; } int main() { cin n m; for (int i 0; i n; i) for (int j 0; j m; j) cin g[i][j]; cout bfs() endl; return 0; }3. 用单独的vis数组有些人不想让d同时承担“距离 是否访问”的作用就会单独开一个vis。#include iostream #include cstring #include queue using namespace std; typedef pairint, int PII; const int N 110; int n, m; int g[N][N], d[N][N]; bool vis[N][N]; int bfs() { queuePII q; memset(d, 0, sizeof d); memset(vis, false, sizeof vis); q.push({0, 0}); vis[0][0] true; d[0][0] 0; int dx[4] {-1, 0, 1, 0}; int dy[4] {0, 1, 0, -1}; while (!q.empty()) { PII t q.front(); q.pop(); for (int i 0; i 4; i) { int x t.first dx[i]; int y t.second dy[i]; if (x 0 x n y 0 y m g[x][y] 0 !vis[x][y]) { vis[x][y] true; d[x][y] d[t.first][t.second] 1; q.push({x, y}); } } } if (!vis[n - 1][m - 1]) return -1; return d[n - 1][m - 1]; } int main() { cin n m; for (int i 0; i n; i) for (int j 0; j m; j) cin g[i][j]; cout bfs() endl; return 0; }4. 手写数组队列这个也很常见尤其是你要避免 STL或者考试里想完全手写模板时。#include iostream #include cstring using namespace std; const int N 110; int n, m; int g[N][N], d[N][N]; pairint, int q[N * N]; int bfs() { memset(d, -1, sizeof d); int hh 0, tt 0; // 队头、队尾 q[0] {0, 0}; d[0][0] 0; int dx[4] {-1, 0, 1, 0}; int dy[4] {0, 1, 0, -1}; while (hh tt) { pairint, int t q[hh]; for (int i 0; i 4; i) { int x t.first dx[i]; int y t.second dy[i]; if (x 0 x n y 0 y m g[x][y] 0 d[x][y] -1) { d[x][y] d[t.first][t.second] 1; q[tt] {x, y}; } } } return d[n - 1][m - 1]; } int main() { cin n m; for (int i 0; i n; i) for (int j 0; j m; j) cin g[i][j]; cout bfs() endl; return 0; }还有一种写法边搜边提前返回就是走到终点就直接返回不等整个 BFS 全跑完。int bfs() { queuepairint, int q; memset(d, -1, sizeof d); q.push({0, 0}); d[0][0] 0; int dx[4] {-1, 0, 1, 0}; int dy[4] {0, 1, 0, -1}; while (!q.empty()) { auto t q.front(); q.pop(); for (int i 0; i 4; i) { int x t.first dx[i]; int y t.second dy[i]; if (x 0 x n y 0 y m g[x][y] 0 d[x][y] -1) { d[x][y] d[t.first][t.second] 1; if (x n - 1 y m - 1) return d[x][y]; q.push({x, y}); } } } return d[n - 1][m - 1]; }#include iostream #include algorithm #include queue #include unordered_map using namespace std; int bfs(string start) { //定义目标状态 string end 12345678x; //定义队列和dist数组 queuestring q; unordered_mapstring, int d; //初始化队列和dist数组 q.push(start); d[start] 0; //转移方式 int dx[4] {1, -1, 0, 0}, dy[4] {0, 0, 1, -1}; while(q.size()) { auto t q.front(); q.pop(); //记录当前状态的距离如果是最终状态则返回距离 int distance d[t]; if(t end) return distance; //查询x在字符串中的下标然后转换为在矩阵中的坐标 int k t.find(x); int x k / 3, y k % 3; for(int i 0; i 4; i) { //求转移后x的坐标 int a x dx[i], b y dy[i]; //当前坐标没有越界 if(a 0 a 3 b 0 b 3) { //转移x swap(t[k], t[a * 3 b]); //如果当前状态是第一次遍历记录距离入队 if(!d.count(t)) { d[t] distance 1; q.push(t); } //还原状态为下一种转换情况做准备 swap(t[k], t[a * 3 b]); } } } //无法转换到目标状态返回-1 return -1; } int main() { string c, start; //输入起始状态 for(int i 0; i 9; i) { cin c; start c; } cout bfs(start) endl; return 0; }