BFS 变形：多源 BFS 与状态图搜索

// 多源 BFS —— 暴力：每个火源单独跑一次 BFS，再取最小值
//
// 输入：第一行 n m
//       接下来 n 行，每行 m 个字符：
//           '.' 空地　'#' 墙　'F' 火源（火源本身也算空地）
// 输出：n 行，每行 m 个整数 —— 每个格子到**最近火源**的最短步数
//       墙输出 -1，走不到的空地也输出 -1，火源本身是 0
//
// 例：
//     F . . .
//     . . . .
//     . . . F
//   每个格子到最近那个 F 的距离（只能上下左右走，不能穿墙）。
//
// 暴力思路：有 k 个火源，就跑 k 次单源 BFS，每次更新一遍全图的最小值。
// 复杂度 O(knm)。火源一多就废了 —— 极端情况下 k = n·m，直接变成 O((nm)²)。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    if (!(cin >> n >> m)) return 0;

    vector<string> g(n);
    for (int i = 0; i < n; i++) cin >> g[i];

    const int INF = INT_MAX;
    vector<vector<int>> best(n, vector<int>(m, INF));
    const int di[4] = {-1, 1, 0, 0}, dj[4] = {0, 0, -1, 1};

    for (int si = 0; si < n; si++)
        for (int sj = 0; sj < m; sj++) {
            if (g[si][sj] != 'F') continue;

            // 从这一个火源出发做一次普通 BFS
            vector<vector<int>> d(n, vector<int>(m, -1));
            queue<pair<int, int>> q;
            d[si][sj] = 0;
            q.push({si, sj});

            while (!q.empty()) {
                auto [i, j] = q.front(); q.pop();
                for (int t = 0; t < 4; t++) {
                    int x = i + di[t], y = j + dj[t];
                    if (x < 0 || x >= n || y < 0 || y >= m) continue;
                    if (g[x][y] == '#' || d[x][y] != -1) continue;
                    d[x][y] = d[i][j] + 1;
                    q.push({x, y});
                }
            }

            for (int i = 0; i < n; i++)
                for (int j = 0; j < m; j++)
                    if (d[i][j] != -1) best[i][j] = min(best[i][j], d[i][j]);
        }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            int v = (g[i][j] == '#' || best[i][j] == INF) ? -1 : best[i][j];
            cout << v << " \n"[j == m - 1];
        }
    }
    return 0;
}

// 多源 BFS —— 所有火源一起入队，只跑一次
//
// 输入输出和 brute.cpp 完全一样，但只扫一遍全图：O(nm)。
//
// ============ 关键的一步 ============
//
// 第 14 章的 BFS 是从**一个**起点开始的：起点入队、距离 0，然后一圈圈往外扩。
//
// 现在有 k 个火源。很多人的第一反应是「跑 k 次 BFS」——
// 但其实**只要把 k 个火源一次性全部塞进队列，距离都设成 0，然后照常 BFS 就行**。
//
// 为什么这样是对的？回想 BFS 的本质：
//   队列里的元素按距离**单调不减**排列，所以第一次到达某个格子时，距离一定最小。
//
// 一开始队列里就是所有距离为 0 的格子（那 k 个火源）—— 这个性质仍然成立。
// 之后弹出它们、扩展出距离 1 的一圈，再扩展出距离 2 的一圈……
// **每个格子第一次被访问时，它到「离它最近的那个火源」的距离就定下来了。**
//
// 换个说法更好理解：想象在图外面加一个「超级源点」，
// 它到每个火源的距离是 0。那么「到最近火源的距离」= 「到超级源点的距离」，
// 于是多源问题就变成了单源问题。
//
// 代码和第 14 章的单源 BFS **只差初始化那几行**。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    if (!(cin >> n >> m)) return 0;

    vector<string> g(n);
    for (int i = 0; i < n; i++) cin >> g[i];

    vector<vector<int>> d(n, vector<int>(m, -1));
    queue<pair<int, int>> q;

    // ★ 唯一的区别：所有火源一起进队，距离都是 0
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (g[i][j] == 'F') { d[i][j] = 0; q.push({i, j}); }

    const int di[4] = {-1, 1, 0, 0}, dj[4] = {0, 0, -1, 1};
    while (!q.empty()) {
        auto [i, j] = q.front(); q.pop();
        for (int t = 0; t < 4; t++) {
            int x = i + di[t], y = j + dj[t];
            if (x < 0 || x >= n || y < 0 || y >= m) continue;
            if (g[x][y] == '#' || d[x][y] != -1) continue;
            d[x][y] = d[i][j] + 1;        // 入队时就定下距离（第 14 章讲过为什么不能等出队）
            q.push({x, y});
        }
    }

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cout << (g[i][j] == '#' ? -1 : d[i][j]) << " \n"[j == m - 1];

    return 0;
}

// 多源 BFS —— 所有火源一起入队，只跑一次
//
// 输入输出和 brute.cpp 完全一样，但只扫一遍全图：O(nm)。
//
// ============ 关键的一步 ============
//
// 第 14 章的 BFS 是从**一个**起点开始的：起点入队、距离 0，然后一圈圈往外扩。
//
// 现在有 k 个火源。很多人的第一反应是「跑 k 次 BFS」——
// 但其实**只要把 k 个火源一次性全部塞进队列，距离都设成 0，然后照常 BFS 就行**。
//
// 为什么这样是对的？回想 BFS 的本质：
//   队列里的元素按距离**单调不减**排列，所以第一次到达某个格子时，距离一定最小。
//
// 一开始队列里就是所有距离为 0 的格子（那 k 个火源）—— 这个性质仍然成立。
// 之后弹出它们、扩展出距离 1 的一圈，再扩展出距离 2 的一圈……
// **每个格子第一次被访问时，它到「离它最近的那个火源」的距离就定下来了。**
//
// 换个说法更好理解：想象在图外面加一个「超级源点」，
// 它到每个火源的距离是 0。那么「到最近火源的距离」= 「到超级源点的距离」，
// 于是多源问题就变成了单源问题。
//
// 代码和第 14 章的单源 BFS **只差初始化那几行**。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    if (!(cin >> n >> m)) return 0;

    vector<string> g(n);
    for (int i = 0; i < n; i++) cin >> g[i];

    vector<vector<int>> d(n, vector<int>(m, -1));
    queue<pair<int, int>> q;

    // ★ 唯一的区别：所有火源一起进队，距离都是 0
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (g[i][j] == 'F') { d[i][j] = 0; q.push({i, j}); }

    const int di[4] = {-1, 1, 0, 0}, dj[4] = {0, 0, -1, 1};
    while (!q.empty()) {
        auto [i, j] = q.front(); q.pop();
        for (int t = 0; t < 4; t++) {
            int x = i + di[t], y = j + dj[t];
            if (x < 0 || x >= n || y < 0 || y >= m) continue;
            if (g[x][y] == '#' || d[x][y] != -1) continue;
            d[x][y] = d[i][j] + 1;        // 入队时就定下距离（第 14 章讲过为什么不能等出队）
            q.push({x, y});
        }
    }

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cout << (g[i][j] == '#' ? -1 : d[i][j]) << " \n"[j == m - 1];

    return 0;
}

// 八数码 —— 在「状态图」上做 BFS
//
// 输入：一行 9 个数字（0 表示空格），按从上到下、从左到右读
//       例如 283104765 表示
//           2 8 3
//           1 0 4
//           7 6 5
// 输出：变成目标状态最少需要多少步；变不成就输出 -1
//
// 目标状态固定为 123804765，也就是
//     1 2 3
//     8 0 4
//     7 6 5
//
// ============ 关键的一步：把「状态」当成图上的点 ============
//
// 第 14 章的 BFS 走在网格上：点 = 格子，边 = 上下左右挪一步。
// 这道题看着完全不同 —— 没有网格，是一个拼图。
//
// 但换个眼光：
//     **一个点 = 整个棋盘的一种摆法（一个 9 位字符串）**
//     **一条边 = 把空格和相邻某一块交换一次**
//
// 于是「最少几步拼好」= 「从起点状态走到目标状态的最短路」。
// 这就是一张图，虽然它不长得像图 —— BFS 原封不动就能用。
//
// 唯一的区别是「访问标记」：网格用 vis[i][j] 数组，
// 而状态是字符串，所以改用 unordered_map<string,int> 记距离。
//
// ★ 这个视角是整个搜索里最值钱的东西之一：
//   **图不一定要画出来。只要你能说清楚「什么是一个状态」和
//   「从一个状态能一步变到哪些状态」，BFS/DFS 就能上。**
//   八数码、倒水问题、魔方、推箱子……全都是这个套路。
//
// 状态总数：9! = 362880（其中一半是无解的）。所以 BFS 最多访问 18 万个状态，很快。

#include <bits/stdc++.h>
using namespace std;

const string GOAL = "123804765";

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string start;
    if (!(cin >> start)) return 0;
    if (start.size() != 9) { cout << -1 << "\n"; return 0; }

    if (start == GOAL) { cout << 0 << "\n"; return 0; }

    unordered_map<string, int> dist;
    dist.reserve(1 << 16);
    queue<string> q;
    dist[start] = 0;
    q.push(start);

    const int di[4] = {-1, 1, 0, 0}, dj[4] = {0, 0, -1, 1};

    while (!q.empty()) {
        string cur = q.front(); q.pop();
        int d = dist[cur];

        int p = (int)cur.find('0');
        int i = p / 3, j = p % 3;

        for (int t = 0; t < 4; t++) {
            int x = i + di[t], y = j + dj[t];
            if (x < 0 || x >= 3 || y < 0 || y >= 3) continue;

            string nxt = cur;
            swap(nxt[p], nxt[x * 3 + y]);        // 空格和那一块交换 —— 这就是一条边

            if (dist.count(nxt)) continue;       // 已经到过，跳过
            dist[nxt] = d + 1;
            if (nxt == GOAL) { cout << d + 1 << "\n"; return 0; }
            q.push(nxt);
        }
    }

    cout << -1 << "\n";                          // 队列空了还没到，说明无解
    return 0;
}

// 八数码 —— 把「按层扩展」打印出来
//
// 输入：一行 9 个数字
// 输出：BFS 每一层新访问了多少个状态，以及最先找到目标的那一层
//
// 跑一遍，看那一列「这一层有多少个新状态」。
// 以 283104765 为例：1, 4, 8, 8, 16 —— 层数一深，状态数就成倍地涨。
// 这就是搜索题的常态，也是为什么剪枝（第 16 章）那么值钱。
//
// 另外注意「已访问状态总数」这个数字：它远小于 9! = 362880，
// 因为一旦碰到目标就停了，根本不用把整张状态图跑完。

#include <bits/stdc++.h>
using namespace std;

const string GOAL = "123804765";

void show(const string& s) {
    for (int i = 0; i < 3; i++) {
        cout << "        ";
        for (int j = 0; j < 3; j++) {
            char c = s[i * 3 + j];
            cout << (c == '0' ? '.' : c) << ' ';
        }
        cout << "\n";
    }
}

int main() {
    string start;
    if (!(cin >> start)) return 0;
    if (start.size() != 9) { cout << "请输入 9 个数字（0 表示空格）\n"; return 0; }

    cout << "起始局面：\n";
    show(start);
    cout << "目标局面：\n";
    show(GOAL);
    cout << "\n";

    unordered_map<string, int> dist;
    queue<string> q;
    dist[start] = 0;
    q.push(start);

    const int di[4] = {-1, 1, 0, 0}, dj[4] = {0, 0, -1, 1};
    int curLayer = 0, layerCount = 1, total = 1, answer = -1;

    cout << "  层  这一层的新状态数  累计访问\n";
    cout << "----  ----------------  --------\n";

    while (!q.empty() && answer < 0) {
        int sz = (int)q.size();
        layerCount = sz;
        cout << setw(4) << curLayer << setw(18) << layerCount << setw(10) << total << "\n";

        for (int c = 0; c < sz && answer < 0; c++) {
            string s = q.front(); q.pop();
            if (s == GOAL) { answer = dist[s]; break; }

            int p = (int)s.find('0');
            int i = p / 3, j = p % 3;
            for (int t = 0; t < 4; t++) {
                int x = i + di[t], y = j + dj[t];
                if (x < 0 || x >= 3 || y < 0 || y >= 3) continue;
                string nxt = s;
                swap(nxt[p], nxt[x * 3 + y]);
                if (dist.count(nxt)) continue;
                dist[nxt] = dist[s] + 1;
                q.push(nxt);
                total++;
            }
        }
        curLayer++;
    }

    cout << "\n";
    if (answer >= 0) {
        cout << "最少 " << answer << " 步。一共访问了 " << total << " 个状态"
             << "（全部可能的局面有 9! = 362880 个，其中一半根本无解）。\n";
    } else {
        cout << "这个局面无解 —— 整张状态图都搜完了也到不了目标。\n";
        cout << "一共访问了 " << total << " 个状态。\n";
    }
    return 0;
}

// 八数码 —— 在「状态图」上做 BFS
//
// 输入：一行 9 个数字（0 表示空格），按从上到下、从左到右读
//       例如 283104765 表示
//           2 8 3
//           1 0 4
//           7 6 5
// 输出：变成目标状态最少需要多少步；变不成就输出 -1
//
// 目标状态固定为 123804765，也就是
//     1 2 3
//     8 0 4
//     7 6 5
//
// ============ 关键的一步：把「状态」当成图上的点 ============
//
// 第 14 章的 BFS 走在网格上：点 = 格子，边 = 上下左右挪一步。
// 这道题看着完全不同 —— 没有网格，是一个拼图。
//
// 但换个眼光：
//     **一个点 = 整个棋盘的一种摆法（一个 9 位字符串）**
//     **一条边 = 把空格和相邻某一块交换一次**
//
// 于是「最少几步拼好」= 「从起点状态走到目标状态的最短路」。
// 这就是一张图，虽然它不长得像图 —— BFS 原封不动就能用。
//
// 唯一的区别是「访问标记」：网格用 vis[i][j] 数组，
// 而状态是字符串，所以改用 unordered_map<string,int> 记距离。
//
// ★ 这个视角是整个搜索里最值钱的东西之一：
//   **图不一定要画出来。只要你能说清楚「什么是一个状态」和
//   「从一个状态能一步变到哪些状态」，BFS/DFS 就能上。**
//   八数码、倒水问题、魔方、推箱子……全都是这个套路。
//
// 状态总数：9! = 362880（其中一半是无解的）。所以 BFS 最多访问 18 万个状态，很快。

#include <bits/stdc++.h>
using namespace std;

const string GOAL = "123804765";

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string start;
    if (!(cin >> start)) return 0;
    if (start.size() != 9) { cout << -1 << "\n"; return 0; }

    if (start == GOAL) { cout << 0 << "\n"; return 0; }

    unordered_map<string, int> dist;
    dist.reserve(1 << 16);
    queue<string> q;
    dist[start] = 0;
    q.push(start);

    const int di[4] = {-1, 1, 0, 0}, dj[4] = {0, 0, -1, 1};

    while (!q.empty()) {
        string cur = q.front(); q.pop();
        int d = dist[cur];

        int p = (int)cur.find('0');
        int i = p / 3, j = p % 3;

        for (int t = 0; t < 4; t++) {
            int x = i + di[t], y = j + dj[t];
            if (x < 0 || x >= 3 || y < 0 || y >= 3) continue;

            string nxt = cur;
            swap(nxt[p], nxt[x * 3 + y]);        // 空格和那一块交换 —— 这就是一条边

            if (dist.count(nxt)) continue;       // 已经到过，跳过
            dist[nxt] = d + 1;
            if (nxt == GOAL) { cout << d + 1 << "\n"; return 0; }
            q.push(nxt);
        }
    }

    cout << -1 << "\n";                          // 队列空了还没到，说明无解
    return 0;
}