連鎖反應 題解｜APCS 2024 年 10 月中高級 第 3 題

前置知識

這題的核心（連鎖反應怎麼模擬、初始半徑怎麼找）下面會從頭講；要先會的是這幾件事，同一個主題兩邊都有的，對照著讀會更快上手：

  • BFS 算格子之間的距離：NTUCPC Guide〈BFS〉——要帶走的是「從起點一圈一圈往外擴，第幾圈拿出來的格子就距離幾步；不能走的格子不進佇列」；吳邦一《AP325》第 7 章 7.2.2「BFS」與例題 P-7-1 探索距離（教材 PDF 第 236～241 頁；Python 版第 7 章（I））。
  • 二維地圖的走訪：出界判斷、方向表；還有佇列。
  • 對答案二分搜（只有最後的「另一種做法」會用到）：NTUCPC Guide〈對答案二分搜〉——要帶走的是「答案序列長得像『否否否……是是是』就能二分」；《AP325》第 4 章 4.2.4「外掛二分搜」（教材 PDF 第 137～139 頁；Python 版第 4 章（II））。

簡潔題意

\(M \times N\) 的格子：恰有一格是寶藏（\(-2\)），有些格子是石頭（\(-1\)，不能走、訊號也穿不過），其餘每格都有一個陷阱，數字是它的影響半徑。陷阱被觸發時，「走 \(x\) 步以內」（上下左右、不穿過石頭、不出界）的格子的陷阱也會被觸發，形成連鎖；半徑 \(0\) 的陷阱不會再觸發別人。寶藏格的陷阱半徑還沒設定：求最小的初始半徑，使得被觸發的陷阱（含寶藏格自己）至少 \(Q\) 個（\(2 \le M, N \le 500\)、\(1 < Q \le MN\)、半徑 \(\le 30\)、半徑為正的格子數 \(K \le 1500\)；答案保證存在）。

依正確通過的測試資料筆數給分，其中：

  • 子題組 1（\(20\) 分）：\(M, N, K \le 100\)，沒有石頭。
  • 子題組 2（\(40\) 分）：\(M, N \le 200\)、\(K \le 500\)，寶藏以外的半徑都不超過 \(20\)。
  • 子題組 3（\(40\) 分）：無額外限制。

先算「離寶藏幾步」，再把連鎖模擬出來

「\(x\) 步以內」是走出來的距離，不是座標相減：有石頭擋著就得繞路，範例 2 的石頭就把寶藏左右兩格隔開了。所以第一步是從寶藏做一次 BFS（石頭不進佇列），得到每一格的 dist0，初始半徑 \(R\) 直接觸發的就是 dist0 <= R 的格子。

被觸發的格子裡，半徑 \(> 0\) 的陷阱會再往外擴散：以它為起點再做一次 BFS，走到第 radius 步就不再往外，走到的每一格都觸發。擴散途中可能觸發新的陷阱，新陷阱又要擴散——用一個佇列 pendingTraps 排隊，一顆一顆處理到佇列空為止。每一格最多被觸發一次、每顆陷阱最多擴散一次，所以不會無限循環。

兩個容易漏的細節：每顆陷阱的 BFS 要用自己的「走過了沒」記號（seen 存「第幾顆陷阱走過」，不用每次清陣列）；擴散的距離是從那顆陷阱算起，跟離寶藏幾步無關（圖 1）。

圖 1：範例 1 初始半徑 2 時，離寶藏 2 步內的 12 格直接觸發，再經四顆陷阱連鎖觸發 7 格，合計 19

先拿下 20 分：半徑從 0 開始一個一個試

有了「給定 \(R\)，算出總共觸發幾個」的函式 count(R)，答案就是第一個讓 count(R) >= Q 的 \(R\)：從 \(0\) 開始試，每試一個就把觸發記號清掉、從頭模擬一次。

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

const int MAX_N = 500;
int M, N, Q;
int a[MAX_N][MAX_N];              // -2 寶藏、-1 石頭、其餘是影響半徑
int dist0[MAX_N][MAX_N];          // 離寶藏幾步（繞過石頭）；-1 = 到不了
bool triggered[MAX_N][MAX_N];
int seen[MAX_N][MAX_N];           // 某顆陷阱擴散時走過這格的記號（記第幾顆）
int stampCounter = 0;
int triggeredCount = 0;
queue<pair<int, int>> pendingTraps;   // 已被觸發、半徑 > 0、還沒擴散的陷阱
const int dr[4] = {-1, 1, 0, 0};
const int dc[4] = {0, 0, -1, 1};

bool inside(int r, int c) {
    return r >= 0 && r < M && c >= 0 && c < N;
}

void trigger(int r, int c) {      // (r, c) 的陷阱被觸發
    if (triggered[r][c]) return;
    triggered[r][c] = true;
    triggeredCount++;
    if (a[r][c] > 0) pendingTraps.push({r, c});
}

void spread(int sr, int sc) {     // 陷阱 (sr, sc) 向外擴散：半徑內、繞過石頭走得到的格子全部觸發
    int radius = a[sr][sc];
    stampCounter++;
    queue<array<int, 3>> q;       // {列, 行, 走了幾步}
    q.push({sr, sc, 0});
    seen[sr][sc] = stampCounter;
    while (!q.empty()) {
        auto [r, c, steps] = q.front();
        q.pop();
        trigger(r, c);
        if (steps == radius) continue;             // 走到半徑盡頭，不再往外
        for (int k = 0; k < 4; k++) {
            int nr = r + dr[k], nc = c + dc[k];
            if (!inside(nr, nc) || a[nr][nc] == -1 || seen[nr][nc] == stampCounter) continue;
            seen[nr][nc] = stampCounter;
            q.push({nr, nc, steps + 1});
        }
    }
}

void chain() {                    // 把排隊中的陷阱一顆一顆擴散完（擴散途中可能又觸發新的）
    while (!pendingTraps.empty()) {
        auto [r, c] = pendingTraps.front();
        pendingTraps.pop();
        spread(r, c);
    }
}

int count(int R) {                // 初始半徑 R 時，總共觸發幾個陷阱（每次從頭模擬）
    for (int r = 0; r < M; r++) {
        for (int c = 0; c < N; c++) triggered[r][c] = false;
    }
    triggeredCount = 0;
    for (int r = 0; r < M; r++) {
        for (int c = 0; c < N; c++) {
            if (dist0[r][c] != -1 && dist0[r][c] <= R) trigger(r, c);
        }
    }
    chain();
    return triggeredCount;
}

int main() {
    cin >> M >> N >> Q;
    int tr = 0, tc = 0;
    for (int r = 0; r < M; r++) {
        for (int c = 0; c < N; c++) {
            cin >> a[r][c];
            if (a[r][c] == -2) {
                tr = r;
                tc = c;
            }
        }
    }
    // 先算每一格離寶藏幾步（繞過石頭）
    for (int r = 0; r < M; r++) {
        for (int c = 0; c < N; c++) dist0[r][c] = -1;
    }
    queue<pair<int, int>> q;
    q.push({tr, tc});
    dist0[tr][tc] = 0;
    int farthest = 0;
    while (!q.empty()) {
        auto [r, c] = q.front();
        q.pop();
        farthest = dist0[r][c];
        for (int k = 0; k < 4; k++) {
            int nr = r + dr[k], nc = c + dc[k];
            if (!inside(nr, nc) || a[nr][nc] == -1 || dist0[nr][nc] != -1) continue;
            dist0[nr][nc] = dist0[r][c] + 1;
            q.push({nr, nc});
        }
    }
    for (int R = 0; R <= farthest; R++) {       // 從小到大試，第一個夠的就是答案
        if (count(R) >= Q) {
            cout << R << endl;
            return 0;
        }
    }
    return 0;
}

一次 count 要掃整張圖 \(O(MN)\)，再加上每顆陷阱的擴散：半徑 \(30\) 以內最多 \(2 \times 30^2 + 2 \times 30 + 1 = 1861\) 格，\(K \le 1500\) 顆合起來不到 \(3 \times 10^6\)。子題組 1 沒有石頭，離寶藏最遠不超過 \(M + N - 2 \le 198\) 步，最多試 \(199\) 次，\(20\) 分穩穩到手。但有石頭時「離寶藏幾步」可以非常大——\(200 \times 200\) 的蛇形走道、\(K = 500\) 的盤面本站實測 \(2.6\) 秒，\(500 \times 500\) 的走道要 \(76\) 秒。

從 20 分到 100 分：半徑放大一步，只多觸發新的一圈

慢在每試一個 \(R\) 都從頭模擬。觀察：\(R\) 變大，被觸發的集合只會變多、不會變少；從 \(R\) 到 \(R + 1\)，新被直接觸發的只有「離寶藏剛好 \(R + 1\) 步」那一圈，之前觸發過的陷阱早就擴散過了。所以不要清掉記號：留著所有狀態，每放大一步只把新的一圈丟進 trigger、跑一次 chain()、看看夠不夠。

「離寶藏剛好 \(R\) 步的那一圈」不用另外找——從寶藏做 BFS 時，格子拿出佇列的順序就是距離由小到大，存進 order 之後用一個指標往後掃就好。

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

const int MAX_N = 500;
int M, N, Q;
int a[MAX_N][MAX_N];              // -2 寶藏、-1 石頭、其餘是影響半徑
int dist0[MAX_N][MAX_N];          // 離寶藏幾步（繞過石頭）；-1 = 到不了
bool triggered[MAX_N][MAX_N];
int seen[MAX_N][MAX_N];           // 某顆陷阱擴散時走過這格的記號（記第幾顆）
int stampCounter = 0;
int triggeredCount = 0;
queue<pair<int, int>> pendingTraps;   // 已被觸發、半徑 > 0、還沒擴散的陷阱
const int dr[4] = {-1, 1, 0, 0};
const int dc[4] = {0, 0, -1, 1};

bool inside(int r, int c) {
    return r >= 0 && r < M && c >= 0 && c < N;
}

void trigger(int r, int c) {      // (r, c) 的陷阱被觸發
    if (triggered[r][c]) return;
    triggered[r][c] = true;
    triggeredCount++;
    if (a[r][c] > 0) pendingTraps.push({r, c});
}

void spread(int sr, int sc) {     // 陷阱 (sr, sc) 向外擴散：半徑內、繞過石頭走得到的格子全部觸發
    int radius = a[sr][sc];
    stampCounter++;
    queue<array<int, 3>> q;       // {列, 行, 走了幾步}
    q.push({sr, sc, 0});
    seen[sr][sc] = stampCounter;
    while (!q.empty()) {
        auto [r, c, steps] = q.front();
        q.pop();
        trigger(r, c);
        if (steps == radius) continue;             // 走到半徑盡頭，不再往外
        for (int k = 0; k < 4; k++) {
            int nr = r + dr[k], nc = c + dc[k];
            if (!inside(nr, nc) || a[nr][nc] == -1 || seen[nr][nc] == stampCounter) continue;
            seen[nr][nc] = stampCounter;
            q.push({nr, nc, steps + 1});
        }
    }
}

void chain() {                    // 把排隊中的陷阱一顆一顆擴散完（擴散途中可能又觸發新的）
    while (!pendingTraps.empty()) {
        auto [r, c] = pendingTraps.front();
        pendingTraps.pop();
        spread(r, c);
    }
}

int main() {
    cin >> M >> N >> Q;
    int tr = 0, tc = 0;
    for (int r = 0; r < M; r++) {
        for (int c = 0; c < N; c++) {
            cin >> a[r][c];
            if (a[r][c] == -2) {
                tr = r;
                tc = c;
            }
        }
    }
    // 先算每一格離寶藏幾步（繞過石頭），順便把格子依距離由近到遠排好
    for (int r = 0; r < M; r++) {
        for (int c = 0; c < N; c++) dist0[r][c] = -1;
    }
    vector<pair<int, int>> order;             // BFS 拿出來的順序就是距離由小到大
    queue<pair<int, int>> q;
    q.push({tr, tc});
    dist0[tr][tc] = 0;
    while (!q.empty()) {
        auto [r, c] = q.front();
        q.pop();
        order.push_back({r, c});
        for (int k = 0; k < 4; k++) {
            int nr = r + dr[k], nc = c + dc[k];
            if (!inside(nr, nc) || a[nr][nc] == -1 || dist0[nr][nc] != -1) continue;
            dist0[nr][nc] = dist0[r][c] + 1;
            q.push({nr, nc});
        }
    }
    // 半徑一圈一圈放大：每放大一步，只多觸發「剛好 R 步遠」的那一圈
    int idx = 0;
    for (int R = 0; idx < (int)order.size(); R++) {
        while (idx < (int)order.size() && dist0[order[idx].first][order[idx].second] == R) {
            trigger(order[idx].first, order[idx].second);
            idx++;
        }
        chain();
        if (triggeredCount >= Q) {
            cout << R << endl;
            return 0;
        }
    }
    return 0;
}

整個過程每一格最多觸發一次、每顆陷阱最多擴散一次，總共 \(O(MN + K \times 1861)\)，不到 \(3 \times 10^6\)，\(500 \times 500\) 的走道本站實測 \(0.03\) 秒。trigger、spread、chain 和 \(20\) 分版一模一樣，換掉的只有「怎麼決定 \(R\)」那一段。

測過再交：範例沒有「要繞路」的距離

範例 1 沒有石頭、範例 2 的石頭只擋住寶藏的左右，兩個範例的答案都是 \(2\)。沒蓋到的：最小盤面、石頭讓最短路明顯比座標相減長、連鎖一步到位、連鎖一路接力，以及離寶藏最遠的格子非常遠的大盤面（驗速度）。

輸入 正確輸出 這一筆在測什麼
2 2 2／-2 0／0 0 1 最小盤面：半徑 \(0\) 只有寶藏自己，\(Q = 2\) 要半徑 \(1\)
3 3 4／-2 -1 0／0 -1 0／0 0 0 3 右上角那格座標相減是 \(2\)，但繞過石頭要走 \(6\) 步；第 \(4\) 個觸發的是 \(3\) 步遠的 \((2, 1)\)
1 6 5／-2 3 0 0 0 0 1 半徑 \(1\) 碰到的陷阱半徑 \(3\)，一口氣再觸發三格；沒有連鎖會答 \(4\)
1 7 7／-2 1 1 1 1 1 1 1 連鎖一路接力：每顆半徑 \(1\) 的陷阱都要再擴散，不能只擴散第一批
用程式造：\(500 \times 500\) 的蛇形走道（奇數列只開一格、其餘是石頭）、寶藏在走道開頭、\(K = 1500\) 顆陷阱平均撒在走道上、\(Q =\) 走道的全部格子數 125249 離寶藏最遠 \(125249\) 步：每個 \(R\) 都從頭模擬的 \(20\) 分版本站實測 \(76\) 秒

五筆都親眼看過正確，這題就穩了。

另一種做法：對答案二分搜

\(20\) 分版的 count(R) 其實只差一步就能滿分：count(R) >= Q 隨著 \(R\) 變大是「否否否……是是是」，所以不必一個一個試，對 \(R\) 做二分搜——左界 \(0\)、右界是離寶藏最遠的距離，每次問中間那個夠不夠，夠就往左縮、不夠就往右縮。count 最多被呼叫 \(\log_2(MN) \le 18\) 次。

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

const int MAX_N = 500;
int M, N, Q;
int a[MAX_N][MAX_N];              // -2 寶藏、-1 石頭、其餘是影響半徑
int dist0[MAX_N][MAX_N];          // 離寶藏幾步（繞過石頭）；-1 = 到不了
bool triggered[MAX_N][MAX_N];
int seen[MAX_N][MAX_N];           // 某顆陷阱擴散時走過這格的記號（記第幾顆）
int stampCounter = 0;
int triggeredCount = 0;
queue<pair<int, int>> pendingTraps;   // 已被觸發、半徑 > 0、還沒擴散的陷阱
const int dr[4] = {-1, 1, 0, 0};
const int dc[4] = {0, 0, -1, 1};

bool inside(int r, int c) {
    return r >= 0 && r < M && c >= 0 && c < N;
}

void trigger(int r, int c) {      // (r, c) 的陷阱被觸發
    if (triggered[r][c]) return;
    triggered[r][c] = true;
    triggeredCount++;
    if (a[r][c] > 0) pendingTraps.push({r, c});
}

void spread(int sr, int sc) {     // 陷阱 (sr, sc) 向外擴散：半徑內、繞過石頭走得到的格子全部觸發
    int radius = a[sr][sc];
    stampCounter++;
    queue<array<int, 3>> q;       // {列, 行, 走了幾步}
    q.push({sr, sc, 0});
    seen[sr][sc] = stampCounter;
    while (!q.empty()) {
        auto [r, c, steps] = q.front();
        q.pop();
        trigger(r, c);
        if (steps == radius) continue;             // 走到半徑盡頭，不再往外
        for (int k = 0; k < 4; k++) {
            int nr = r + dr[k], nc = c + dc[k];
            if (!inside(nr, nc) || a[nr][nc] == -1 || seen[nr][nc] == stampCounter) continue;
            seen[nr][nc] = stampCounter;
            q.push({nr, nc, steps + 1});
        }
    }
}

void chain() {                    // 把排隊中的陷阱一顆一顆擴散完（擴散途中可能又觸發新的）
    while (!pendingTraps.empty()) {
        auto [r, c] = pendingTraps.front();
        pendingTraps.pop();
        spread(r, c);
    }
}

int count(int R) {                // 初始半徑 R 時，總共觸發幾個陷阱（每次從頭模擬）
    for (int r = 0; r < M; r++) {
        for (int c = 0; c < N; c++) triggered[r][c] = false;
    }
    triggeredCount = 0;
    for (int r = 0; r < M; r++) {
        for (int c = 0; c < N; c++) {
            if (dist0[r][c] != -1 && dist0[r][c] <= R) trigger(r, c);
        }
    }
    chain();
    return triggeredCount;
}

int main() {
    cin >> M >> N >> Q;
    int tr = 0, tc = 0;
    for (int r = 0; r < M; r++) {
        for (int c = 0; c < N; c++) {
            cin >> a[r][c];
            if (a[r][c] == -2) {
                tr = r;
                tc = c;
            }
        }
    }
    // 先算每一格離寶藏幾步（繞過石頭）
    for (int r = 0; r < M; r++) {
        for (int c = 0; c < N; c++) dist0[r][c] = -1;
    }
    queue<pair<int, int>> q;
    q.push({tr, tc});
    dist0[tr][tc] = 0;
    int farthest = 0;
    while (!q.empty()) {
        auto [r, c] = q.front();
        q.pop();
        farthest = dist0[r][c];
        for (int k = 0; k < 4; k++) {
            int nr = r + dr[k], nc = c + dc[k];
            if (!inside(nr, nc) || a[nr][nc] == -1 || dist0[nr][nc] != -1) continue;
            dist0[nr][nc] = dist0[r][c] + 1;
            q.push({nr, nc});
        }
    }
    int low = 0, high = farthest;                   // 答案在 [low, high] 裡
    while (low < high) {
        int mid = (low + high) / 2;
        if (count(mid) >= Q) high = mid;            // mid 夠：答案不會比 mid 大
        else low = mid + 1;                         // mid 不夠：答案至少 mid + 1
    }
    cout << low << endl;
    return 0;
}

兩種都是滿分：二分搜版從 \(20\) 分版只改最後幾行，\(500 \times 500\) 的走道本站實測 \(0.05\) 秒；一圈一圈放大的版本連 \(\log\) 都省掉、也不用清記號，但要先想通「狀態可以留著」這件事。

常犯錯誤
  • 距離用座標相減、不管石頭：兩個範例都過（範例 2 的石頭剛好沒擋住任何一個算進答案的格子），計分測資掛 \(4\) 筆；自測表第 2 列印 2。
  • 沒有連鎖（只算寶藏半徑內的格子）：範例 1 印 3、範例 2 印 3。
  • 陷阱擴散時沒有限制步數（整個連通的區域全部觸發）：兩個範例都過，計分測資掛 \(12\) 筆；大盤面每顆陷阱都要掃整張圖，還會超時。
  • 半徑少算一步（steps + 1 == radius 就停）：範例 1 印 3、範例 2 印 3。
  • 所有陷阱共用同一份「走過了沒」記號（不清、也不換記號）：後面的陷阱走不進前面陷阱走過的格子；範例 1 印 3。
  • 用「限制深度的 DFS」找陷阱 \(x\) 步內的格子：DFS 先走到的不一定是最短路，繞遠路到的格子被提早標記，真正 \(x\) 步內的格子反而進不去。兩個範例都過，計分測資掛 \(9\) 筆。
  • 每個 \(R\) 都從頭模擬的 \(20\) 分版硬交：長走道的計分測資本站實測 \(6 \sim 10\) 秒，超時。