标签：广度优先搜索
题意：给定一个矩形地图，地图中$.$代表可以走的空地；$\#$代表不可以走的墙壁；$1$表示小爱初始的位置；$2$表示小艾初始的位置。小爱和小艾可以上下左右走或原地不动，不可以移动到对方当前的位置，求经过多少轮之后，小爱和小艾可以实现互换位置。
题解：把小爱和小艾的整体移动跑$bfs$，开个四维$vis$数组标记一下各自走同步的情况，进行位移的过程中需要把各自$4$个方向，即$4$x$4$种情况都跑一下。跑$bfs$的过程中需要注意几个细节：

1. 如果小爱或者小艾某个人已经跑到对应互换的终点了，就原地保持不动。
2. 如果发生了当前跑到的两个位置互换的情况，要跳过。比如小爱在$(2,2)$位置要往右走到$(2,3)$；小艾在$(2,3)$位置要往左走到$(2,3)$。
3. 移动到同一个格子的时候，需要让其中一个人原地不动，另一个人走到这个各自上。

整道题细节比较多和需要考虑的点比较多，同学们在写的过程中要注意细节的处理。
代码：

#include <bits/stdc++.h>
using namespace std;struct node {// 当前小爱坐标(x1,y1) 小艾坐标(x2,y2) 步数int x1, y1, x2, y2, step;
}st;
int n, m;
int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};
char a[50][50];
bool vis[50][50][50][50];bool check(int x, int y) {return x >= 1 && x <= n && y >= 1 && y <= m && a[x][y] != '#';
}void bfs() {queue<node> q;q.push(st);vis[st.x1][st.y1][st.x2][st.y2] = 1;while (!q.empty()) {node p = q.front();q.pop();if (p.x1 == st.x2 && p.y1 == st.y2 && p.x2 == st.x1 && p.y2 == st.y1) {cout << p.step;return ;}// 枚举小爱和小艾的所有方向组合for (int i = 0; i < 4; i++)for (int j = 0; j < 4; j++) {int nx1 = p.x1 + dx[i], ny1 = p.y1 + dy[i];int nx2 = p.x2 + dx[j], ny2 = p.y2 + dy[j];if (nx1 == p.x2 && ny1 == p.y2 && nx2 == p.x1 && ny2 == p.y1) continue;// 如果已经到终点, 原地保持不动if (p.x1 == st.x2 && p.y1 == st.y2) nx1 = p.x1, ny1 = p.y1;if (p.x2 == st.x1 && p.y2 == st.y1) nx2 = p.x2, ny2 = p.y2;if (check(nx1, ny1) && check(nx2, ny2)) {if (nx1 == nx2 && ny1 == ny2) { // 移动到同一个格子的情况if (!vis[nx1][ny1][p.x2][p.y2]) {vis[nx1][ny1][p.x2][p.y2] = 1;q.push({nx1, ny1, p.x2, p.y2, p.step + 1});}if (!vis[p.x1][p.y1][nx2][ny2]) {vis[p.x1][p.y1][nx2][ny2] = 1;q.push({p.x1, p.y1, nx2, ny2, p.step + 1});}} else { // 不是移动到同一个格子的情况if (!vis[nx1][ny1][nx2][ny2]) {vis[nx1][ny1][nx2][ny2] = 1;q.push({nx1, ny1, nx2, ny2, p.step + 1});}}}}}cout << "No Solution";
}int main() {cin >> n >> m;for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++) {cin >> a[i][j];if (a[i][j] == '1') st.x1 = i, st.y1 = j;if (a[i][j] == '2') st.x2 = i, st.y2 = j;}bfs();return 0;
}