洛谷 B3625 迷宫寻路

// ★ B3625 正解：把网格当图跑一次 BFS（或 DFS，都行 —— 这道题只问「通不通」，不问最短）。
//
// 本章那句话在这道题上是白送的：**网格是图的一个特例**，
// 「邻居」就是上下左右四格，剩下的和 fast.cpp 一模一样。
//
//     从 (0,0) 出发泛洪，最后看 (n-1, m-1) 有没有被标记。
//
// ⚠ 三处最容易写错的地方（本页各配了一个错误版本）：
//   ① **先判界，再看格子** —— 反过来写就是越界读（b3625Bound.cpp）；
//   ② **入队就标记** —— 忘了标记会死循环 / 爆栈（b3625NoVis.cpp）；
//   ③ 四个方向，别顺手写成八个（b3625Eight.cpp）。
//
// ⚠ 而题面那句「保证 (1,1) 和 (n,m) 均为空地」是**命门**：
//   这一版从 (0,0) 直接入队，压根没检查它是不是墙。解析页第 ⑤ 步把这句话称了一遍。
//
// 复杂度 O(nm)。顶格 n = m = 100 ⇒ 10⁴ 格。

#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 dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};
    vector<vector<char>> vis(n, vector<char>(m, 0));
    queue<pair<int, int>> q;
    q.push({0, 0});
    vis[0][0] = 1;                                    // ★ 入队就标记
    while (!q.empty()) {
        auto [x, y] = q.front(); q.pop();
        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d], ny = y + dy[d];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;   // ① 先判界
            if (g[nx][ny] == '#' || vis[nx][ny]) continue;          //    再看格子
            vis[nx][ny] = 1;
            q.push({nx, ny});
        }
    }
    printf("%s\n", vis[n - 1][m - 1] ? "Yes" : "No");
    return 0;
}

// ✗ B3625 错法一：**忘了标记走过的格子**。
//
// 泛洪的三句话是「看邻居 → 没去过就去 → 去了就标记」。少了最后一句，
// A 把 B 推进队列、B 又把 A 推回来，**队列永远空不了**。
//
// ⚠ 它的现形方式不是「答案错」，是**卡死或者内存爆掉** ——
//   而这正是对拍最不擅长的那一类（[第 20 章 P5019](/sol/p5019/) 那条）。
//   所以这一版加了一道保险：入队超过 10⁷ 次就打 `LOOP` 退出，
//   ★ 否则它会把 check:viz 整个挂住（[第 4 章 P1731](/sol/p1731/) 踩过一次）。

#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 dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};
    vector<vector<char>> seen(n, vector<char>(m, 0));   // 只用来判答案，不当守卫
    queue<pair<int, int>> q;
    q.push({0, 0});
    seen[0][0] = 1;
    long long pushes = 1;
    while (!q.empty()) {
        auto [x, y] = q.front(); q.pop();
        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d], ny = y + dy[d];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if (g[nx][ny] == '#') continue;
            /* ★ 少了这一句：if (seen[nx][ny]) continue; */
            seen[nx][ny] = 1;
            q.push({nx, ny});
            if (++pushes > 10000000) { printf("LOOP\n"); return 0; }
        }
    }
    printf("%s\n", seen[n - 1][m - 1] ? "Yes" : "No");
    return 0;
}

// ✗ B3625 错法二：**先看格子，再判界** —— 顺序反了就是越界读。
//
//     if (g[nx][ny] == '#' || vis[nx][ny]) continue;      // ← 这一句先跑了
//     if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
//
// `g` 是 `vector<string>`，`nx = -1` 时 `g[-1]` 是**未定义行为** ——
// 它可能崩、可能读到垃圾、也可能什么事都没有。
//
// ⚠⚠ 而「什么事都没有」才是最坏的情况：本机跑一百遍全对，交上去 RE 在第 3 个点。
//   ⇒ 这一版用 `.at()` 把 UB 变成**确定的异常**，好让它在页面上真的现形一次
//     （[第 45 章](/ch/45-estimate/)那条：演示错误写法时，要让那个错**可复现**）。

#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 dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};
    vector<vector<char>> vis(n, vector<char>(m, 0));
    queue<pair<int, int>> q;
    q.push({0, 0});
    vis[0][0] = 1;
    try {
        while (!q.empty()) {
            auto [x, y] = q.front(); q.pop();
            for (int d = 0; d < 4; d++) {
                int nx = x + dx[d], ny = y + dy[d];
                if (g.at(nx).at(ny) == '#' || vis.at(nx).at(ny)) continue;   // ★ 先看格子
                if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;        //   才判界
                vis[nx][ny] = 1;
                q.push({nx, ny});
            }
        }
    } catch (const std::out_of_range&) {
        printf("越界了（真机上这里是未定义行为，可能崩、可能读到垃圾、也可能装作没事）\n");
        return 0;
    }
    printf("%s\n", vis[n - 1][m - 1] ? "Yes" : "No");
    return 0;
}

// ✗ B3625 错法三：**顺手写成了八个方向**（连斜着也能走）。
//
// 题面写的是「只能从一个空地走到其上、下、左、右的空地」—— 四个方向。
// 八连通把图变宽了，于是它**只会多说 Yes，不会多说 No** ⇒ 答案**恒 ≥ 正解**
//（把 Yes 当作「更大」）。
//
// ⚠⚠ 这个错法在同一张题单里是有来处的：[P1443 马的遍历](/sol/p1443/) 那道题，
//   「邻居」正是八个（日字）方向 —— **上一道题的方向数组，就是这一道题的 bug**。

#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 dx[8] = {-1, 1, 0, 0, -1, -1, 1, 1};
    const int dy[8] = {0, 0, -1, 1, -1, 1, -1, 1};
    vector<vector<char>> vis(n, vector<char>(m, 0));
    queue<pair<int, int>> q;
    q.push({0, 0});
    vis[0][0] = 1;
    while (!q.empty()) {
        auto [x, y] = q.front(); q.pop();
        for (int d = 0; d < 8; d++) {                 // ★ 8 而不是 4
            int nx = x + dx[d], ny = y + dy[d];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if (g[nx][ny] == '#' || vis[nx][ny]) continue;
            vis[nx][ny] = 1;
            q.push({nx, ny});
        }
    }
    printf("%s\n", vis[n - 1][m - 1] ? "Yes" : "No");
    return 0;
}