洛谷 P1141 01迷宫

// ⚠ P1141 第一版：**每次询问从那一格跑一遍 BFS**，数一数走过几个格子。
//
// 这是照着题面一个字一个字翻译出来的：「询问从某一格开始能移动到多少个格子」——
// 那就从那一格开始走一遍。**答案永远是对的**，对拍跑多少轮都抓不到它。
//
// 复杂度 O(mn²)。顶格 n = 1000、m = 10⁵ ⇒ **10¹¹**，一秒钟连零头都跑不完。
//
// ★★ 但**别急着删它** —— 题面那五档数据范围里，有一档是**按 m 分的**：
//     「对于 **50%** 的数据，**m ≤ 5**」
//   那一档它只要 5 × 10⁶ 次，**哪怕 n 顶格也稳稳拿 50 分**。
//   ⇒ ★★★ 出题人等于直接告诉你：**这个暴力的瓶颈是 m，不是 n。**
//
// ★ 它同时是本页的对拍参照物（和「一次染色」那条路一行代码都不共享）。
//
// ⚠ 命令行给一个 `count` 参数，它就只打「一共走过多少个格子」。

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

int main(int argc, char** argv) {
    bool countOnly = (argc > 1 && string(argv[1]) == "count");
    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};
    string out;
    long long steps = 0;
    vector<pair<int, int>> st;
    vector<vector<char>> vis(n, vector<char>(n, 0));
    for (int t = 0; t < m; t++) {
        int qi, qj;
        cin >> qi >> qj;
        --qi; --qj;                                   // 题面是 1-based
        for (int i = 0; i < n; i++) fill(vis[i].begin(), vis[i].end(), 0);
        int cnt = 0;
        st.clear(); st.push_back({qi, qj}); vis[qi][qj] = 1;
        while (!st.empty()) {
            auto [x, y] = st.back(); st.pop_back();
            cnt++;
            for (int d = 0; d < 4; d++) {
                int nx = x + dx[d], ny = y + dy[d];
                if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
                steps++;
                if (g[nx][ny] == g[x][y] || vis[nx][ny]) continue;   // ★ 只能走到「不同」的格子
                vis[nx][ny] = 1;
                st.push_back({nx, ny});
            }
        }
        out += to_string(cnt);
        out += '\n';
    }
    if (countOnly) { printf("%lld\n", steps); return 0; }
    fwrite(out.data(), 1, out.size(), stdout);
    return 0;
}

// ★★ P1141 正解：**一次扫描，给每个连通块编号 + 记住它有多大**，询问 O(1)。
//
// ★★★ 凭什么能这么干 —— 这一步不证清楚就只是碰运气：
//   「从 A 走得到 B」这件事在这张图上是**对称的**（相邻且数字不同 ⇒ 两边互相走得通），
//   于是「互相可达」是一个**等价关系** ⇒ 格子被划分成若干**连通块**，
//   而**同一个块里每个格子的答案都等于这个块的大小**。
//   ⚠ 这一条离开对称性就塌了 —— [上一轮 P3916](/sol/p3916/) 那张**有向图**上，
//     「v 能到谁」和「谁能到 v」是两个不同的问题，压根没有「块大小」这回事。
//
//     for (每个还没编号的格子) { 泛洪一次，把整块染成同一个编号，顺便数出块的大小 }
//     答案(i, j) = size[ id[i][j] ]
//
// 复杂度 O(n² + m)：顶格 10⁶ + 10⁵。⇒ 比「每次询问跑一遍」快 **10⁵ 倍**。
//
// ⚠ DFS 写成**迭代**的：顶格 n = 1000 ⇒ 一个块可能有 10⁶ 个格子，
//   递归到底会爆栈（[B3625](/sol/b3625/) 第 ⑥ 步量过门槛：本机 17.4 万层）。见 p1141Rec.cpp。
// ⚠ 答案上界 n² = 10⁶ ⇒ `int` 绰绰有余。

#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<int>> id(n, vector<int>(n, -1));
    vector<int> sz;
    vector<pair<int, int>> st;

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) {
            if (id[i][j] >= 0) continue;
            int cur = (int)sz.size(), cnt = 0;
            st.clear(); st.push_back({i, j}); id[i][j] = cur;
            while (!st.empty()) {
                auto [x, y] = st.back(); st.pop_back();
                cnt++;
                for (int d = 0; d < 4; d++) {
                    int nx = x + dx[d], ny = y + dy[d];
                    if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
                    if (g[nx][ny] == g[x][y] || id[nx][ny] >= 0) continue;
                    id[nx][ny] = cur;
                    st.push_back({nx, ny});
                }
            }
            sz.push_back(cnt);                        // ★ 整块共用这一个数
        }

    string out;
    for (int t = 0; t < m; t++) {
        int qi, qj;
        cin >> qi >> qj;
        out += to_string(sz[id[qi - 1][qj - 1]]);     // ★ 题面是 1-based
        out += '\n';
    }
    fwrite(out.data(), 1, out.size(), stdout);
    return 0;
}

// ✗ P1141 错法一：把「只能走到**不同**的数字」写成了「走到**相同**的数字」。
//
//     if (g[nx][ny] == g[x][y]) continue;   // 正解：相同就不能走
//     if (g[nx][ny] != g[x][y]) continue;   // ★ 这一版：不同就不能走
//
// 一个字符之差。⇒ 它算的是**同色连通块**的大小 —— 一个完全不同、但同样有意义的量。
// ★ 说清楚它算了什么之后，「什么时候它会蒙对」就是白送的：
//   `1 × 1` 的迷宫（只有自己）两边都是 1；棋盘格（黑白相间）上它恒等于 1。

#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<int>> id(n, vector<int>(n, -1));
    vector<int> sz;
    vector<pair<int, int>> st;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) {
            if (id[i][j] >= 0) continue;
            int cur = (int)sz.size(), cnt = 0;
            st.clear(); st.push_back({i, j}); id[i][j] = cur;
            while (!st.empty()) {
                auto [x, y] = st.back(); st.pop_back();
                cnt++;
                for (int d = 0; d < 4; d++) {
                    int nx = x + dx[d], ny = y + dy[d];
                    if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
                    if (g[nx][ny] != g[x][y] || id[nx][ny] >= 0) continue;   // ★ 反了
                    id[nx][ny] = cur;
                    st.push_back({nx, ny});
                }
            }
            sz.push_back(cnt);
        }
    string out;
    for (int t = 0; t < m; t++) {
        int qi, qj;
        cin >> qi >> qj;
        out += to_string(sz[id[qi - 1][qj - 1]]);
        out += '\n';
    }
    fwrite(out.data(), 1, out.size(), stdout);
    return 0;
}