Editorial for 魔王迷宮 (APCS 2021-09 中級)

簡潔題意

\(n \times m\) 的棋盤上有 \(k\) 隻魔王，第 \(i\) 隻從 \((r_i, c_i)\) 出發、每回合固定移動 \((s_i, t_i)\)。每回合依序：① 所有魔王同時在腳下放一顆炸彈 ② 同時各自移動一次 ③ 移出棋盤的魔王消失 ④ 其餘魔王中，移到已有炸彈格子的會引爆——該格的所有魔王與炸彈同時消失。持續到棋盤上沒有魔王為止，輸出還放有至少一顆炸彈的格子數（同一格幾顆都只算一格；\(1 \le n, m \le 100\)、\(1 \le k \le 500\)、\(-100 \le s_i, t_i \le 100\)）。

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

  • 子題組 1（\(50\) 分）：\(n = 1\)，且所有魔王的 \(r_i = 0\)、\(s_i = 0\)。
  • 子題組 2（\(50\) 分）：無額外限制。

先拿下子題組 1（50 分）：棋盤只有一列

\(n = 1\) 而且 \(s_i = 0\)，所有魔王都在同一列上左右移動——每隻魔王只剩「位置 c」和「每回合位移 t」兩個數字，炸彈表也只是一條 bomb[m]。照題目的四個步驟逐字翻譯就好：

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, m, k;
    cin >> n >> m >> k;                     // 子題組 1 保證 n = 1：棋盤只有一列
    vector<int> c(k), t(k);                 // 第 i 隻魔王的位置與每回合的位移
    for (int i = 0; i < k; i++) {
        int r, s;
        cin >> r >> c[i] >> s >> t[i];      // r、s 一定是 0，照格式讀掉就好
    }

    vector<bool> bomb(m, false);            // 這格有沒有炸彈
    vector<bool> alive(k, true);
    int alive_count = k;

    while (alive_count > 0) {
        for (int i = 0; i < k; i++) {       // 步驟 1、2：放炸彈，然後移動
            if (!alive[i]) continue;
            bomb[c[i]] = true;
            c[i] += t[i];
        }
        vector<int> hit;                    // 這一回合被踩到的格子
        for (int i = 0; i < k; i++) {       // 步驟 3、4：出界的消失；踩到炸彈的消失
            if (!alive[i]) continue;
            if (c[i] < 0 || c[i] >= m) {
                alive[i] = false;
                alive_count--;
            } else if (bomb[c[i]]) {
                alive[i] = false;
                alive_count--;
                hit.push_back(c[i]);
            }
        }
        for (int i = 0; i < (int)hit.size(); i++) {   // 全部判定完才清炸彈
            bomb[hit[i]] = false;
        }
    }

    int answer = 0;
    for (int j = 0; j < m; j++) {
        if (bomb[j]) answer++;
    }
    cout << answer << '\n';
    return 0;
}

三個地方別踩：

  • 放炸彈在前、移動在後：出界的魔王也會在出界前那一格留下炸彈（範例 1 的第三隻）。
  • 「已有炸彈」包含這一回合剛放的：向量是 \(0\) 的魔王放完炸彈原地不動，第 ④ 步就踩到自己的炸彈、當場消失（範例 1 的第一隻）。這也是迴圈一定會停的理由——會動的魔王每回合至少走一格，遲早出界；不會動的第一回合就消失。
  • 同時判定：這一回合誰踩到炸彈先全部記下來，判完才一起清——兩隻魔王同一回合踩進同一個有炸彈的格子，兩隻都要消失。判到一隻就清一格的話，第二隻踩到的已經是空地。

這份程式交上去，範例 2 和 \(n > 1\) 的測資會 WA——這是正常的，逐筆給分之下子題組 1 的 \(50\) 分穩穩到手。

從 50 分到 100 分：位置變二維，其餘照舊

完整版只是把「一條線」換成「一張棋盤」：位置從 c 變成 (r, c)、位移從 t 變成 (s, t)，炸彈表從一維 bomb[m] 變成和棋盤一樣大的 bomb[n][m]（13.5：再開一張和地圖一樣大的表，記「這格有沒有東西」）；出界判斷從只查 c 變成列、行都查。每隻魔王就是一條沿固定向量一直走的射線，出界就結束——四個步驟的骨架和子題版一模一樣：

// APCS 2021-09 中級 P2 魔王迷宮：k 隻魔王同時沿固定向量前進；「同時判定」＝先全部移動、再一起檢查
#include <iostream>
#include <utility>
#include <vector>
using namespace std;

int main() {
    int n, m, k;
    cin >> n >> m >> k;
    vector<int> r(k), c(k), s(k), t(k);   // 第 i 隻魔王的位置與移動向量
    vector<bool> alive(k, true);
    for (int i = 0; i < k; i++) cin >> r[i] >> c[i] >> s[i] >> t[i];

    vector<vector<bool>> bomb(n, vector<bool>(m, false));       // 這格有沒有炸彈
    vector<vector<bool>> exploded(n, vector<bool>(m, false));   // 這一回合被引爆的格子
    int alive_count = k;

    while (alive_count > 0) {
        // 步驟 1、2：所有活著的魔王放炸彈，然後同時移動一步
        for (int i = 0; i < k; i++) {
            if (!alive[i]) continue;
            bomb[r[i]][c[i]] = true;
            r[i] += s[i];
            c[i] += t[i];
        }

        // 步驟 3、4：出界的消失；踩到炸彈的消失，並記下要清掉的格子
        vector<pair<int, int>> cells_to_clear;
        for (int i = 0; i < k; i++) {
            if (!alive[i]) continue;
            if (r[i] < 0 || r[i] >= n || c[i] < 0 || c[i] >= m) {
                alive[i] = false;
                alive_count--;
            } else if (bomb[r[i]][c[i]]) {
                alive[i] = false;
                alive_count--;
                if (!exploded[r[i]][c[i]]) {
                    exploded[r[i]][c[i]] = true;
                    cells_to_clear.push_back({r[i], c[i]});
                }
            }
        }

        // 全部判定完才清炸彈：兩隻魔王同回合踩同一格，兩隻都要消失
        for (int i = 0; i < (int)cells_to_clear.size(); i++) {
            int x = cells_to_clear[i].first;
            int y = cells_to_clear[i].second;
            bomb[x][y] = false;
            exploded[x][y] = false;
        }
    }

    int answer = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (bomb[i][j]) answer++;
    cout << answer << '\n';
    return 0;
}

跟子題版比多出來的東西：

  • r、s 真的用上了：位置與位移各兩個座標，出界要 r、c 都查——只查 c 的話，範例 2 的魔王會走到第 \(6\) 列直接讀到棋盤外面。
  • cells_to_clear 用 pair 記格子（10.11），exploded 表只是讓同一格不被記兩次；子題版一維時把同一格清兩次也無妨，所以省了它。
  • \(k\) 隻魔王的資料用四個 vector 平行存放，r[i]、c[i]、s[i]、t[i] 是同一隻的四個欄位。

會不會跑不完？每回合掃 \(k \le 500\) 隻魔王，會動的魔王在 \(100 \times 100\) 的棋盤上最多 \(100\) 回合就出界、不會動的第一回合就消失，總量離一秒遠得很。

測過再交：範例沒有兩隻魔王同時踩同一格

兩個範例合起來：踩到炸彈的只有「向量是 \(0\)、踩自己」那一種（範例 1 第一隻），而且那一格之後又被別的魔王重新放了炸彈——所以引爆後有沒有把炸彈清掉，範例看不出來；兩隻魔王同一回合踩進同一格也沒有出現過。自己造：

輸入 正確輸出 這一筆在測什麼
1 3 1 ／ 0 1 0 0 0 一隻不會動的魔王：放炸彈、原地踩爆、炸彈跟著消失——引爆後沒清炸彈的程式會印 1
1 3 3 ／ 0 0 0 1 ／ 0 2 0 -1 ／ 0 1 0 0 2 三隻同一回合都踩進位置 \(1\)：全部消失、位置 \(1\) 清空，剩 \(0\)、\(2\) 兩格——判一隻清一格的程式會印 1
2 2 1 ／ 1 1 -1 -1 2 往左上走、兩個座標一起變負出界：\((1,1)\)、\((0,0)\) 各一顆炸彈
1 5 1 ／ 0 3 0 100 1 一步就跳出棋盤：只留下起點那一顆

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

常犯錯誤
  • 判到一隻踩到炸彈就當場清掉那格：兩個範例都會過；自測表第 2 列印 1（該印 2）——同一回合第二隻踩到的已經是空地。
  • 引爆後不清炸彈：兩個範例都會過（範例 1 那格後來又被放了一顆）；自測表第 1 列印 1（該印 0）。
  • 先移動再放炸彈：出界的魔王留不下炸彈、原地不動的魔王也踩不到自己——範例 1 印 0、範例 2 印 0。
  • 只判出界、忘了判踩炸彈：向量是 \(0\) 的魔王永遠不會消失，範例 1 直接跑不完（在 OJ 上是 TLE）。
  • 算的是放了幾顆炸彈、不是幾格有炸彈：範例 2 印 4（該印 3），題目的範例解釋自己就在講這件事。
  • 出界只查行不查列（子題版的習慣帶進完整版）：範例 1 過（它只有一列），範例 2 的魔王走到第 \(6\) 列直接讀到棋盤外面、程式當掉。