BFS 广度优先搜索：迷宫最短路

// 迷宫最短路 —— 暴力：DFS 枚举每一条路，取最短的那条
//
// 输入：第一行 n m，接下来 n 行每行 m 个字符，'1' 能走，'0' 是墙
// 输出：从左上角 (0,0) 走到右下角 (n-1,m-1) 的最少步数；走不到输出 -1
//       每步只能上下左右走一格。
//
// 这是最诚实的暴力：既然要「最短」，那我把所有能走的路线全都走一遍，
// 记录下其中最短的那条就行了。用 DFS 枚举，走过的格子标记上不再重复走
// （否则会绕圈子绕到天荒地老），从一条分支回来时再把标记撤销。
//
// 它慢在哪？慢在它枚举的是「所有路径」，而路径的条数是指数级的。
// 一个 5×5 的空网格，从左上到右下有 8512 条路；
// 6×6 有 1262816 条；7×7 有 575780564 条 —— 五亿七千万条。
// 边长每加一，工作量乘以几百倍。这就是「指数爆炸」，
// 不是「电脑再快一点就行」能救的。
//
// 更要命的是：这五亿条路里，绝大多数一看就不可能是最短的 ——
// 暴力却老老实实每一条都走到底。

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

const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};

int n, m;
vector<string> g;
vector<vector<char>> vis;
int best;

void dfs(int i, int j, int steps) {
    if (i == n - 1 && j == m - 1) {        // 走到终点了
        best = min(best, steps);
        return;
    }
    for (int d = 0; d < 4; d++) {
        int x = i + dx[d], y = j + dy[d];
        if (x < 0 || x >= n || y < 0 || y >= m) continue;
        if (g[x][y] != '1') continue;      // 是墙
        if (vis[x][y]) continue;           // 这条路上已经踩过了，不能绕圈

        vis[x][y] = 1;                     // 踩上去
        dfs(x, y, steps + 1);
        vis[x][y] = 0;                     // 退回来，把脚印擦掉（回溯）
    }
}

int main() {
    if (!(cin >> n >> m)) return 0;
    g.resize(n);
    for (int i = 0; i < n; i++) cin >> g[i];

    if (g[0][0] != '1' || g[n - 1][m - 1] != '1') { cout << -1 << "\n"; return 0; }

    vis.assign(n, vector<char>(m, 0));
    best = INT_MAX;
    vis[0][0] = 1;
    dfs(0, 0, 0);

    cout << (best == INT_MAX ? -1 : best) << "\n";
    return 0;
}

// 迷宫最短路 —— BFS
//
// 和 brute.cpp 解同一道题，答案必须一样，但快得没法比。
//
// 关键的那一步想法：
//   暴力的错误不在于「用了 DFS」，而在于它一头扎到底、把每条路都走完才敢下结论。
//   可是「最短」这件事有个特别好的性质 —— 我们可以按距离一圈一圈地往外找：
//
//     先站在起点（距离 0）；
//     把所有距离 1 的格子全找出来；
//     再把所有距离 2 的格子全找出来；
//     ……
//
//   这样一来，只要终点第一次被找到，它所在的那一圈的编号就是最短距离。
//   不需要再看任何别的路 —— 因为更外面的圈只会更远。
//
//   ★ 第一次到达 = 最短到达。这就是 BFS 全部的秘密。
//
// 怎么实现「一圈一圈」？用一个队列：
//   先进队列的格子先被处理，而先进队列的一定是距离更近的，
//   所以队列天然帮你把格子按距离排好了序。
//
//   注意 vis 标记要在「入队时」打上，不是在「出队时」——
//   否则同一个格子会被不同的邻居重复塞进队列，退化成暴力。这是 BFS 的头号错误。
//
// 复杂度：每个格子最多进队一次，O(nm)。

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

const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};

int main() {
    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<string> g(n);
    for (int i = 0; i < n; i++) cin >> g[i];

    if (g[0][0] != '1' || g[n - 1][m - 1] != '1') { cout << -1 << "\n"; return 0; }

    vector<vector<int>> dist(n, vector<int>(m, -1));   // -1 = 还没到过
    queue<pair<int, int>> q;

    dist[0][0] = 0;
    q.push({0, 0});

    while (!q.empty()) {
        auto [i, j] = q.front();
        q.pop();

        if (i == n - 1 && j == m - 1) break;   // 第一次碰到终点，就已经是最短了

        for (int d = 0; d < 4; d++) {
            int x = i + dx[d], y = j + dy[d];
            if (x < 0 || x >= n || y < 0 || y >= m) continue;
            if (g[x][y] != '1') continue;
            if (dist[x][y] != -1) continue;    // 来过了，而且那次一定不比这次远

            dist[x][y] = dist[i][j] + 1;       // ← 入队时就定下距离并标记
            q.push({x, y});
        }
    }

    cout << dist[n - 1][m - 1] << "\n";
    return 0;
}

// 迷宫最短路 —— 带打印的 BFS，用来「看见」一圈一圈扩散
//
// 它按层输出：第 0 层只有起点，第 1 层是所有距离 1 的格子……
// 每层结束后打印一次当前的距离图。跑一遍你会看到一圈波纹从起点荡开。
//
// 对比第 13 章 DFS 的 trace：
//   DFS 是「一条道走到黑再退回来」，BFS 是「所有方向齐头并进」。
//   同样是搜索，一个用递归（栈），一个用队列 —— 差别全在这里。

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

const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};

int main() {
    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<string> g(n);
    for (int i = 0; i < n; i++) cin >> g[i];

    if (g[0][0] != '1' || g[n - 1][m - 1] != '1') {
        cout << "起点或终点是墙，直接无解\n-1\n";
        return 0;
    }

    vector<vector<int>> dist(n, vector<int>(m, -1));
    queue<pair<int, int>> q;
    dist[0][0] = 0;
    q.push({0, 0});

    int layer = 0;
    while (!q.empty()) {
        int sz = (int)q.size();          // 当前这一圈有多少个格子
        cout << "===== 第 " << layer << " 圈（距离 " << layer << "），共 " << sz << " 个格子 =====\n";

        cout << "  这一圈的格子：";
        vector<pair<int, int>> cur;
        for (int k = 0; k < sz; k++) { cur.push_back(q.front()); q.pop(); }
        for (auto& [i, j] : cur) cout << "(" << i << "," << j << ") ";
        cout << "\n";

        for (auto& [i, j] : cur) {
            for (int d = 0; d < 4; d++) {
                int x = i + dx[d], y = j + dy[d];
                if (x < 0 || x >= n || y < 0 || y >= m) continue;
                if (g[x][y] != '1' || dist[x][y] != -1) continue;
                dist[x][y] = layer + 1;
                q.push({x, y});
            }
        }

        cout << "  扩散后的距离图（# 是墙，. 是还没到过）：\n";
        for (int i = 0; i < n; i++) {
            cout << "    ";
            for (int j = 0; j < m; j++) {
                if (g[i][j] != '1') cout << " #";
                else if (dist[i][j] < 0) cout << " .";
                else cout << " " << (char)('0' + dist[i][j] % 10);
            }
            cout << "\n";
        }

        if (dist[n - 1][m - 1] != -1) {
            cout << "\n终点第一次被碰到，距离 = " << dist[n - 1][m - 1] << "，可以收工了。\n";
            break;
        }
        layer++;
    }

    cout << "\n答案 = " << dist[n - 1][m - 1] << "\n";
    return 0;
}

// 迷宫最短路 —— BFS
//
// 和 brute.cpp 解同一道题，答案必须一样，但快得没法比。
//
// 关键的那一步想法：
//   暴力的错误不在于「用了 DFS」，而在于它一头扎到底、把每条路都走完才敢下结论。
//   可是「最短」这件事有个特别好的性质 —— 我们可以按距离一圈一圈地往外找：
//
//     先站在起点（距离 0）；
//     把所有距离 1 的格子全找出来；
//     再把所有距离 2 的格子全找出来；
//     ……
//
//   这样一来，只要终点第一次被找到，它所在的那一圈的编号就是最短距离。
//   不需要再看任何别的路 —— 因为更外面的圈只会更远。
//
//   ★ 第一次到达 = 最短到达。这就是 BFS 全部的秘密。
//
// 怎么实现「一圈一圈」？用一个队列：
//   先进队列的格子先被处理，而先进队列的一定是距离更近的，
//   所以队列天然帮你把格子按距离排好了序。
//
//   注意 vis 标记要在「入队时」打上，不是在「出队时」——
//   否则同一个格子会被不同的邻居重复塞进队列，退化成暴力。这是 BFS 的头号错误。
//
// 复杂度：每个格子最多进队一次，O(nm)。

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

const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};

int main() {
    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<string> g(n);
    for (int i = 0; i < n; i++) cin >> g[i];

    if (g[0][0] != '1' || g[n - 1][m - 1] != '1') { cout << -1 << "\n"; return 0; }

    vector<vector<int>> dist(n, vector<int>(m, -1));   // -1 = 还没到过
    queue<pair<int, int>> q;

    dist[0][0] = 0;
    q.push({0, 0});

    while (!q.empty()) {
        auto [i, j] = q.front();
        q.pop();

        if (i == n - 1 && j == m - 1) break;   // 第一次碰到终点，就已经是最短了

        for (int d = 0; d < 4; d++) {
            int x = i + dx[d], y = j + dy[d];
            if (x < 0 || x >= n || y < 0 || y >= m) continue;
            if (g[x][y] != '1') continue;
            if (dist[x][y] != -1) continue;    // 来过了，而且那次一定不比这次远

            dist[x][y] = dist[i][j] + 1;       // ← 入队时就定下距离并标记
            q.push({x, y});
        }
    }

    cout << dist[n - 1][m - 1] << "\n";
    return 0;
}