14 、BFS

queue <类型> Q;
Q.push(最初状态);
while(!Q.empty()){
    类型 u=Q.front(); Q.pop();
    for(枚举所有可扩展到的状态){
        if(满足入队条件){
            Q.push(状态); //维护某些必要信息 
        }
    } 
}

#include <bits/stdc++.h>
using namespace std;
const int N = 405;
struct node {
    int x, y;
    int s; // 走了多少步
};
int g[N][N];
int dir[8][2] = {{-1, -2},
                 {-2, -1},
                 {-2, 1},
                 {-1, 2},
                 {1, 2},
                 {2, 1},
                 {2, -1},
                 {1, -2}}; // 8个方向
int x, y, n, m;
queue<node> q;
int main() {
    cin >> n >> m >> x >> y;
    memset(g, -1, sizeof(g)); // 让数组都变成-1，也可以两层循环，但不能设成其他值（会出错）
    g[x][y] = 0;
    q.push({x, y, 0});
    while (!q.empty()) {
        node now = q.front();
        q.pop();
        int x = now.x, y = now.y, s = now.s; // 取出队头元素
        for (int i = 0; i <= 7; i++) {
            int nx = x + dir[i][0];
            int ny = y + dir[i][1];
            if (nx < 1 || nx > n || ny < 1 || ny > m || g[nx][ny] != -1)
                continue;            // 越界或者已经走过
            g[nx][ny] = s + 1;       // 记录步数
            q.push({nx, ny, s + 1}); // 入队
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cout << g[i][j] << " ";
        }
        cout << endl;
    }
}

#include <bits/stdc++.h>
using namespace std;
int N, A, B, w[205];

struct node {  // 定义一个结构体，用于存储队列中的元素
    int floor; // 当前楼层
    int time;  // 到达当前楼层所需的时间
};

queue<node> q; // 定义一个队列，用于广度优先搜索
bool vis[205]; // 定义一个布尔数组，用于标记是否已经访问过某一层

int main() {
    cin >> N >> A >> B;
    for (int i = 1; i <= N; i++) {
        cin >> w[i];
    }

    q.push({A, 0}); // 将起始楼层加入队列，并初始化时间为0
    vis[A] = 1;     // 标记起始楼层为已访问

    while (!q.empty()) {      // 当队列不为空时，进行循环
        node now = q.front(); // 获取队列的第一个元素
        q.pop();              // 将该元素从队列中移除
        int f = now.floor;    
        int t = now.time;     

        if (f == B) {  // 如果当前楼层是目标楼层
            cout << t; // 输出到达目标楼层所需的时间
            return 0;  // 结束程序
        }
        // 尝试向上跳
        if (f + w[f] <= N && vis[f + w[f]] == 0) { // 如果可以向上跳，并且目标楼层未被访问
            vis[f + w[f]] = 1;                     // 标记为已访问
            q.push({f + w[f], t + 1});             // 将新楼层加入队列，并增加时间
        }
        // 尝试向下跳
        if (f - w[f] >= 1 && vis[f - w[f]] == 0) { // 如果可以向下跳，并且目标楼层未被访问
            vis[f - w[f]] = 1;                     // 标记为已访问
            q.push({f - w[f], t + 1});             // 将新楼层加入队列，并增加时间
        }
    }
    cout << -1 << endl; // 如果队列为空，说明无法到达目标楼层，输出-1
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
struct node {
    int x, y;
};
int dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
char g[N][N];
bool vis[N][N];
int n, ans;
int bfs(int sx, int sy) {
    queue<node> q;
    q.push({sx, sy});
    vis[sx][sy] = 1;
    bool flag = 0;
    while (!q.empty()) {
        node now = q.front();
        q.pop();
        int x = now.x, y = now.y;
        if (g[x + 1][y] == '#' && g[x - 1][y] == '#' && g[x][y + 1] == '#' && g[x][y - 1] == '#')
            flag = 1;
        for (int i = 0; i <= 3; i++) {
            int nx = x + dir[i][0];
            int ny = y + dir[i][1];
            if (nx < 1 || nx > n || ny < 1 || ny > n || vis[nx][ny] || g[nx][ny] == '.')
                continue;
            vis[nx][ny] = 1;
            q.push({nx, ny});
        }
    }
    if (flag == 1)
        return false;
    else
        return true;
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        scanf("%s", g[i] + 1);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            if (g[i][j] == '#' && vis[i][j] == 0) {
                if (bfs(i, j))
                    ans++;
            }
        }
    cout << ans << endl;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
struct node {
    string s;
    int k;
};
int dir[4][2] = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
string start, goal;
queue<node> q;
map<string, int> m;
int main() {
    cin >> start >> goal;
    q.push({start, 0});
    m[start] = 1;
    while (!q.empty()) {
        node now = q.front();
        q.pop();
        string s = now.s;
        int k = now.k;
        int p = 0, x, y;
        if (s == goal) {
            cout << k << endl;
            return 0;
        }
        for (int i = 0; i < s.size(); i++)
            if (s[i] == '.')
                p = i;
        x = p / 3 + 1, y = p % 3 + 1;
        for (int i = 0; i <= 3; i++) {
            int nx = x + dir[i][0];
            int ny = y + dir[i][1];
            if (nx < 1 || nx > 3 || ny < 1 || ny > 3)
                continue;
            int np = (nx - 1) * 3 + ny - 1;
            string ns = s;
            swap(ns[p], ns[np]);
            if (m[ns])
                continue;
            m[ns] = 1;
            q.push({ns, k + 1});
        }
    }
    cout << -1 << endl;
    return 0;
}