洛谷 P1332 血色先锋队

// ⚠ 第一版：每个感染源各跑一次 BFS，把结果取 min（**答案是对的，就是跑不完**）
//
// 这是最直接的想法 —— 「BFS 会算一个源到全图的距离，那 a 个源就跑 a 次呗」。
//
// ★ 它的答案**完全正确**，所以对拍一个字都说不出来（这一页第 ⑥ 步：精确的 0）。
//   量它只能换一把尺子：**数一共入了多少次队**。
//
// 复杂度 O(a × nm)：顶格 a = 10⁵、nm = 250000 ⇒ **2.5 × 10¹⁰** 次入队。
// ⇒ 而多源 BFS 是 O(nm) = 250000 次，和 a 有多大**没有关系** —— 差 a 倍。
//
// ⚠ 这一版自带一道闸：入队次数超上限就报出来并退出，
//   绝不「悄悄少跑几个源」把自己救活（[P1443](/sol/p1443/) 那条教训）。

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

const int DX[4] = {-1, 1, 0, 0};
const int DY[4] = {0, 0, -1, 1};
const long long PUSH_LIMIT = 200000000LL;

int main() {
    int n, m, a, b;
    if (scanf("%d %d %d %d", &n, &m, &a, &b) != 4) return 0;

    vector<pair<int, int>> src(a);
    for (auto& [x, y] : src)
        if (scanf("%d %d", &x, &y) != 2) return 0;

    vector<vector<int>> best(n + 1, vector<int>(m + 1, INT_MAX));
    vector<vector<int>> dist_(n + 1, vector<int>(m + 1));
    long long pushes = 0;

    for (auto [sx, sy] : src) {                   // ⚠ 一个源一次 BFS —— a 次
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++) dist_[i][j] = -1;

        queue<pair<int, int>> q;
        dist_[sx][sy] = 0;
        q.push({sx, sy});
        pushes++;
        while (!q.empty()) {
            auto [x, y] = q.front();
            q.pop();
            for (int k = 0; k < 4; k++) {
                int nx = x + DX[k], ny = y + DY[k];
                if (nx < 1 || nx > n || ny < 1 || ny > m) continue;
                if (dist_[nx][ny] != -1) continue;
                dist_[nx][ny] = dist_[x][y] + 1;
                q.push({nx, ny});
                if (++pushes > PUSH_LIMIT) {
                    fprintf(stderr, "入队次数超过 %lld —— 这一档它根本跑不完\n", PUSH_LIMIT);
                    return 1;
                }
            }
        }
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++) best[i][j] = min(best[i][j], dist_[i][j]);
    }

    for (int i = 0; i < b; i++) {
        int x, y;
        if (scanf("%d %d", &x, &y) != 2) return 0;
        printf("%d\n", best[x][y]);
    }
    return 0;
}

// ⚠⚠ 错法：把「每个源各跑一次 BFS」顺手「优化」成共用一个 dist 数组
//
// 上一版（p1332Each.cpp）每个源都要把 dist 清一遍、跑一遍全图，慢得离谱。
// 于是很自然会想：「已经算过距离的格子就别再算了呗」——
// 把 dist 数组提到循环外面，`if (dist[nx][ny] != -1) continue;` 照旧：
//
//     for (每个感染源 s)
//         if (dist[s] == -1) { dist[s] = 0; BFS(s); }     // ⚠ dist 不清空
//
// 看着像是把重复劳动省掉了，**而它算出来的根本不是「到最近感染源的距离」**：
//
//   ★ 第一个源的那趟 BFS 会把**整张图**铺满（网格是连通的，没有障碍）；
//     等轮到第二个源，`dist[s]` 早就不是 -1 了 —— 它一步都走不了。
//   ⇒ 结果**等于「只有第一个感染源」**，后面 a − 1 个源全部作废。
//
// ★ 草稿在这儿写过一句「而它在样例上照样能对」—— **实测把它打回来了**：
//   官方样例三个询问它全给错（`4 6 4`，正确是 `3 1 3`），因为样例的第一个源在角上 (1,1)，
//   而三个询问点都离第二个源 (5,4) 更近。⇒ **这一版是样例就挡得住的**。
//   ⚠ 但别把「样例挡得住」当成它无害：只要输入里第一个源恰好离询问点最近，它就对了 ——
//   到底占多大比例是量出来的，见 p1332Count.cpp 第 ③ 段。

#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, a, b;
    if (scanf("%d %d %d %d", &n, &m, &a, &b) != 4) return 0;

    vector<vector<int>> dist_(n + 1, vector<int>(m + 1, -1));

    for (int i = 0; i < a; i++) {
        int sx, sy;
        if (scanf("%d %d", &sx, &sy) != 2) return 0;
        if (dist_[sx][sy] != -1) continue;        // ⚠⚠ 就是这一句：第二个源起全被挡在门外
        dist_[sx][sy] = 0;
        queue<pair<int, int>> q;
        q.push({sx, sy});
        while (!q.empty()) {
            auto [x, y] = q.front();
            q.pop();
            for (int k = 0; k < 4; k++) {
                int nx = x + DX[k], ny = y + DY[k];
                if (nx < 1 || nx > n || ny < 1 || ny > m) continue;
                if (dist_[nx][ny] != -1) continue;
                dist_[nx][ny] = dist_[x][y] + 1;
                q.push({nx, ny});
            }
        }
    }

    for (int i = 0; i < b; i++) {
        int x, y;
        if (scanf("%d %d", &x, &y) != 2) return 0;
        printf("%d\n", dist_[x][y]);
    }
    return 0;
}

// P1332 血色先锋队 —— 多源 BFS（★ 这一版就能 AC）
//
// 题目：n × m 的矩阵，给 a 个感染源；瘟疫每小时向上下左右扩散一格，
//       问 b 个指定位置各在第几小时被感染。n, m ≤ 500，a, b ≤ 10⁵。
//
// ★ 关键的一步：**把 a 个感染源一开始就全塞进队列**，然后照常 BFS 一次。
//
//   为什么这样是对的：想象凭空加一个「超级源点」，它和每个感染源之间连一条长度 0 的边。
//   从超级源点做 BFS，第 0 层就是全部感染源、第 1 层是它们的邻居……
//   ⇒ **BFS「按距离一圈一圈往外」这件事一点没变**，变的只是第 0 层不止一个格子。
//   ⇒ 每个格子第一次被碰到时，拿到的就是「到最近的那个感染源」的距离。
//
// 复杂度 O(nm)：整张图只走一遍，和 a 有多大**没有关系**。
// ⚠ 对比第 ① 版（每个源各跑一次 BFS）：那是 O(a × nm)，顶格 10⁵ × 250000 = 2.5 × 10¹⁰。
//
// ⚠ a 个感染源里**可能有重复坐标**（题面没保证互异）——「入队时就标记」天然挡掉了重复。

#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, a, b;
    if (scanf("%d %d %d %d", &n, &m, &a, &b) != 4) return 0;

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

    for (int i = 0; i < a; i++) {                 // ★ 所有感染源一起当第 0 层
        int x, y;
        if (scanf("%d %d", &x, &y) != 2) return 0;
        if (dist_[x][y] != -1) continue;          // 重复的源，跳过
        dist_[x][y] = 0;
        q.push({x, y});
    }

    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();
        for (int k = 0; k < 4; k++) {
            int nx = x + DX[k], ny = y + DY[k];
            if (nx < 1 || nx > n || ny < 1 || ny > m) continue;
            if (dist_[nx][ny] != -1) continue;
            dist_[nx][ny] = dist_[x][y] + 1;      // 入队时就定下距离
            q.push({nx, ny});
        }
    }

    for (int i = 0; i < b; i++) {                 // b 个询问都是 O(1) 查表
        int x, y;
        if (scanf("%d %d", &x, &y) != 2) return 0;
        printf("%d\n", dist_[x][y]);
    }
    return 0;
}

// 验算用的第二条路：直接取「到最近感染源的曼哈顿距离」
//
// ★★★ 这道题的网格**没有任何障碍**，四个方向都能走。
//   在这种网格上，从 (x1,y1) 走到 (x2,y2) 的最短步数就是
//
//       |x1 - x2| + |y1 - y2|
//
//   ⇒ 答案 = 对所有感染源取这个式子的最小值。**一行公式，一个队列都不用。**
//
// ⚠ 但它**不能当解法**：b 个询问 × a 个源 = 10⁵ × 10⁵ = **10¹⁰** 次减法，跑不完。
//   （这正是这道题要用 BFS 的理由 —— 不是因为公式不对，是因为规模不对。）
//
// ★ 那它有什么用？**当对拍的参照物。**
//   它和多源 BFS **一行代码都不共享**，走的是完全不同的一条路 ——
//   这正是[第 7 章 P1147](/sol/p1147/) 那条：「验算最好走一条和算法完全无关的路」。
//
// ⚠⚠ 而这条等价**是有前提的**：网格里不能有障碍。
//   随便挖一堵墙，「最短步数 = 曼哈顿距离」立刻不成立（p1332Count.cpp 第 ④ 段量了一个反例）。
//   ⇒ 用一条捷径去验算之前，先问清楚**这条捷径的前提是什么**。

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

int main() {
    int n, m, a, b;
    if (scanf("%d %d %d %d", &n, &m, &a, &b) != 4) return 0;
    (void)n; (void)m;

    vector<pair<int, int>> src(a);
    for (auto& [x, y] : src)
        if (scanf("%d %d", &x, &y) != 2) return 0;

    for (int i = 0; i < b; i++) {
        int x, y;
        if (scanf("%d %d", &x, &y) != 2) return 0;
        int best = INT_MAX;
        for (auto [sx, sy] : src) best = min(best, abs(sx - x) + abs(sy - y));
        printf("%d\n", best);
    }
    return 0;
}

// P1332 对拍生成器：`./p1332Gen <seed> [maxN] [maxA] [maxB]`
//
// 输出一整份输入：`n m a b`、a 行感染源、b 行询问。
//
// ★ 这一页最要紧的旋钮是 **a（感染源个数）**，默认 4：
//   ⚠ `a = 1` 时 `p1332Shared.cpp`（那个「共用 dist 数组」的错法）**是完全正确的** ——
//     它错在「第二个源起全被挡在门外」，而根本没有第二个源。
//   ⇒ 只造一个感染源的生成器，对那个 bug 是**精确的 0**（p1332Count.cpp 第 ③ 段量了这条曲线）。
//
// 坐标允许重复（题面没保证感染源互异），正解靠「入队时就标记」天然挡掉。

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

int main(int argc, char** argv) {
    unsigned seed = argc > 1 ? (unsigned)atoi(argv[1]) : 1u;
    int maxN = argc > 2 ? atoi(argv[2]) : 8;
    int maxA = argc > 3 ? atoi(argv[3]) : 4;
    int maxB = argc > 4 ? atoi(argv[4]) : 6;
    if (maxN < 1) maxN = 1;
    if (maxA < 1) maxA = 1;
    if (maxB < 1) maxB = 1;

    mt19937 rng(seed);
    int n = (int)(rng() % (unsigned)maxN) + 1;
    int m = (int)(rng() % (unsigned)maxN) + 1;
    int a = (int)(rng() % (unsigned)maxA) + 1;
    int b = (int)(rng() % (unsigned)maxB) + 1;

    printf("%d %d %d %d\n", n, m, a, b);
    for (int i = 0; i < a + b; i++)
        printf("%d %d\n", (int)(rng() % (unsigned)n) + 1, (int)(rng() % (unsigned)m) + 1);
    return 0;
}

// P1332 的度量程序 —— 这一页所有数字都出自这一份。
//
// `./p1332Count`      人看的版本
// `./p1332Count csv`  一行一项，给 scripts/check-viz.mjs 写断言用
//
// 五段：
//   ① 入队次数：多源 BFS 是 O(nm)，「每个源各跑一次」是 O(a × nm) —— 正好差 a 倍；
//   ② ★★★ 无障碍网格上，多源 BFS 的结果**逐格等于**「到最近感染源的曼哈顿距离」；
//   ③ ⚠ 而这条等价**有前提**：随便挖一堵墙就不成立（给一个具体反例）；
//   ④ 「共用 dist 数组」那个错法**究竟算了什么**：逐格等于「只有第一个感染源」；
//      以及它的抓获率沿 a 走 —— **a = 1 那一档是精确的 0**；
//   ⑤ 顶格那一档的读入有多大。

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

static bool CSV = false;
static const int DX[4] = {-1, 1, 0, 0};
static const int DY[4] = {0, 0, -1, 1};

static void row(const char* key, const vector<long long>& v) {
    if (!CSV) return;
    printf("%s", key);
    for (long long x : v) printf(",%lld", x);
    printf("\n");
}

/** 多源 BFS。wall = '1' 的格子不能走（这道题本身没有墙，第 ③ 段才用得上）。 */
static pair<vector<vector<int>>, long long> multiBfs(
        int n, int m, const vector<pair<int, int>>& src, const vector<string>* wall = nullptr) {
    vector<vector<int>> d(n + 1, vector<int>(m + 1, -1));
    queue<pair<int, int>> q;
    long long pushes = 0;
    for (auto [x, y] : src) {
        if (d[x][y] != -1) continue;
        d[x][y] = 0;
        q.push({x, y});
        pushes++;
    }
    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();
        for (int k = 0; k < 4; k++) {
            int a = x + DX[k], b = y + DY[k];
            if (a < 1 || a > n || b < 1 || b > m) continue;
            if (wall && (*wall)[a - 1][b - 1] == '1') continue;
            if (d[a][b] != -1) continue;
            d[a][b] = d[x][y] + 1;
            q.push({a, b});
            pushes++;
        }
    }
    return {d, pushes};
}

/** 每个源各跑一次 BFS，取 min。只关心入队次数。 */
static long long eachPushes(int n, int m, const vector<pair<int, int>>& src) {
    long long pushes = 0;
    for (auto [sx, sy] : src) {
        vector<vector<int>> d(n + 1, vector<int>(m + 1, -1));
        queue<pair<int, int>> q;
        d[sx][sy] = 0;
        q.push({sx, sy});
        pushes++;
        while (!q.empty()) {
            auto [x, y] = q.front();
            q.pop();
            for (int k = 0; k < 4; k++) {
                int a = x + DX[k], b = y + DY[k];
                if (a < 1 || a > n || b < 1 || b > m) continue;
                if (d[a][b] != -1) continue;
                d[a][b] = d[x][y] + 1;
                q.push({a, b});
                pushes++;
            }
        }
    }
    return pushes;
}

/** 「共用 dist 数组」那个错法。 */
static vector<vector<int>> sharedBfs(int n, int m, const vector<pair<int, int>>& src) {
    vector<vector<int>> d(n + 1, vector<int>(m + 1, -1));
    for (auto [sx, sy] : src) {
        if (d[sx][sy] != -1) continue;
        d[sx][sy] = 0;
        queue<pair<int, int>> q;
        q.push({sx, sy});
        while (!q.empty()) {
            auto [x, y] = q.front();
            q.pop();
            for (int k = 0; k < 4; k++) {
                int a = x + DX[k], b = y + DY[k];
                if (a < 1 || a > n || b < 1 || b > m) continue;
                if (d[a][b] != -1) continue;
                d[a][b] = d[x][y] + 1;
                q.push({a, b});
            }
        }
    }
    return d;
}

int main(int argc, char** argv) {
    CSV = (argc > 1 && string(argv[1]) == "csv");

    /* ① 入队次数：多源 vs 每个源各跑一次 */
    {
        vector<long long> multi, each, ratio;
        vector<array<int, 3>> cases = {{20, 20, 1}, {20, 20, 4}, {20, 20, 16}, {50, 50, 10}};
        if (!CSV) printf("① 入队次数（多源 BFS 一次铺满 vs 每个源各跑一次）\n");
        for (auto [n, m, a] : cases) {
            mt19937 rng(12345u + (unsigned)a);
            vector<pair<int, int>> src;
            for (int i = 0; i < a; i++)
                src.push_back({(int)(rng() % (unsigned)n) + 1, (int)(rng() % (unsigned)m) + 1});
            long long p1 = multiBfs(n, m, src).second;
            long long p2 = eachPushes(n, m, src);
            multi.push_back(p1);
            each.push_back(p2);
            ratio.push_back(p2 / p1);
            if (!CSV)
                printf("   %d × %d，a = %2d：多源 %6lld 次，每源各一次 %8lld 次，倍数 %lld\n",
                       n, m, a, p1, p2, p2 / p1);
        }
        if (!CSV)
            printf("   ⇒ 顶格 n = m = 500、a = 10⁵：多源 250000 次，"
                   "每源各一次 %lld 次\n\n", 250000LL * 100000LL);
        row("pushMulti", multi);
        row("pushEach", each);
        row("pushRatio", ratio);
        row("worstEach", {250000LL * 100000LL});
    }

    /* ② 无障碍网格上：多源 BFS ≡ 到最近感染源的曼哈顿距离 */
    {
        long long cells = 0, same = 0;
        for (int n = 1; n <= 12; n++)
            for (int m = 1; m <= 12; m++)
                for (int a = 1; a <= 4; a++) {
                    mt19937 rng((unsigned)(n * 10000 + m * 100 + a));
                    vector<pair<int, int>> src;
                    for (int i = 0; i < a; i++)
                        src.push_back({(int)(rng() % (unsigned)n) + 1, (int)(rng() % (unsigned)m) + 1});
                    auto d = multiBfs(n, m, src).first;
                    for (int x = 1; x <= n; x++)
                        for (int y = 1; y <= m; y++) {
                            int best = INT_MAX;
                            for (auto [sx, sy] : src) best = min(best, abs(sx - x) + abs(sy - y));
                            cells++;
                            if (d[x][y] == best) same++;
                        }
                }
        if (!CSV)
            printf("② 无障碍网格上，多源 BFS ≡ min 曼哈顿距离：逐格比了 %lld 格，一致 %lld 格\n\n",
                   cells, same);
        row("manhattanSame", {cells, same});
    }

    /* ③ ⚠ 那条等价的前提：挖一堵墙就不成立 */
    {
        //   . 1 .        (1,1) 是感染源，'1' 是墙：(1,2) 和 (2,2)
        //   . 1 .        想从 (1,1) 到 (1,3)，只能绕最下面那一行
        //   . . .
        vector<string> wall = {".1.", ".1.", "..."};
        vector<pair<int, int>> src = {{1, 1}};
        auto d = multiBfs(3, 3, src, &wall).first;
        int bfs13 = d[1][3];
        int man13 = abs(1 - 1) + abs(1 - 3);
        if (!CSV)
            printf("③ 挖一堵墙之后（3 × 3，墙在 (1,2) 和 (2,2)，源在 (1,1)）：\n"
                   "   到 (1,3) 的真实步数 %d，曼哈顿距离只有 %d —— 那条等价立刻不成立\n\n",
                   bfs13, man13);
        row("wallCase", {bfs13, man13});
    }

    /* ④ 「共用 dist」那个错法究竟算了什么 ＋ 它的抓获率沿 a 走 */
    {
        // (a) 它逐格等于「只有第一个感染源」
        long long cells = 0, same = 0;
        for (int n = 1; n <= 10; n++)
            for (int m = 1; m <= 10; m++)
                for (int a = 1; a <= 5; a++) {
                    mt19937 rng((unsigned)(n * 777 + m * 31 + a));
                    vector<pair<int, int>> src;
                    for (int i = 0; i < a; i++)
                        src.push_back({(int)(rng() % (unsigned)n) + 1, (int)(rng() % (unsigned)m) + 1});
                    auto bad = sharedBfs(n, m, src);
                    auto only1 = multiBfs(n, m, {src[0]}).first;
                    for (int x = 1; x <= n; x++)
                        for (int y = 1; y <= m; y++) {
                            cells++;
                            if (bad[x][y] == only1[x][y]) same++;
                        }
                }
        if (!CSV)
            printf("④ 「共用 dist」那版逐格等于「只有第一个感染源」：比了 %lld 格，一致 %lld 格\n",
                   cells, same);
        row("sharedIsFirst", {cells, same});

        // (b) 抓获率沿 a 走（300 轮，网格 8 × 8，每轮 6 个询问）
        vector<long long> caught;
        vector<int> as = {1, 2, 3, 5, 10};
        if (!CSV) printf("   它的抓获率沿「感染源个数 a」走（8 × 8，300 轮）：\n");
        for (int a : as) {
            int c = 0;
            for (int seed = 1; seed <= 300; seed++) {
                mt19937 rng((unsigned)seed * 131u + (unsigned)a);
                int n = 8, m = 8;
                vector<pair<int, int>> src;
                for (int i = 0; i < a; i++)
                    src.push_back({(int)(rng() % (unsigned)n) + 1, (int)(rng() % (unsigned)m) + 1});
                auto ok = multiBfs(n, m, src).first;
                auto bad = sharedBfs(n, m, src);
                bool differ = false;
                for (int i = 0; i < 6 && !differ; i++) {
                    int x = (int)(rng() % (unsigned)n) + 1, y = (int)(rng() % (unsigned)m) + 1;
                    if (ok[x][y] != bad[x][y]) differ = true;
                }
                if (differ) c++;
            }
            caught.push_back(c);
            if (!CSV) printf("     a = %2d：%3d / 300\n", a, c);
        }
        if (!CSV) printf("   ⇒ a = 1 那一档是**精确的 0** —— 它错在「第二个源」，而根本没有第二个源\n\n");
        row("sharedCatch", caught);
    }

    /* ⑤ 顶格那一档的读入 */
    {
        // 第 1 行 "500 500 100000 100000\n"，然后 a + b 行，每行最长 "500 500\n" = 8 字节
        long long lines = 200000;
        long long bytes = (long long)strlen("500 500 100000 100000\n") + lines * 8;
        if (!CSV)
            printf("⑤ 顶格 a = b = 10⁵：读入 %lld 行坐标、%lld 个整数，最多 %lld 字节（%.2f MB）\n",
                   lines, lines * 2, bytes, (double)bytes / 1048576.0);
        row("inputBytes", {lines, lines * 2, bytes});
    }
    return 0;
}