魔王迷宮 題解|APCS 2021 年 9 月中級 第 2 題


簡潔題意

\(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>
using namespace std;

const int MAX_M = 100, MAX_K = 500;
int c[MAX_K], t[MAX_K];                     // 第 i 隻魔王的位置與每回合的位移
bool bomb[MAX_M];                           // 這格有沒有炸彈(全域陣列:一開始全是 false)
bool alive[MAX_K];

int main() {
    int n, m, k;
    cin >> n >> m >> k;                     // 子題組 1 保證 n = 1:棋盤只有一列
    for (int i = 0; i < k; i++) {
        int r, s;
        cin >> r >> c[i] >> s >> t[i];      // r、s 一定是 0,照格式讀掉就好
        alive[i] = 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];
        }
        int hit[MAX_K];                     // 這一回合被踩到的格子
        int hit_count = 0;
        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[hit_count] = c[i];
                hit_count++;
            }
        }
        for (int i = 0; i < hit_count; 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](再開一張和地圖一樣大的表,記「這格有沒有東西」);出界判斷從只查 c 變成列、行都查。每隻魔王就是一條沿固定向量一直走的射線,出界就結束——四個步驟的骨架和子題組版一模一樣:

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

const int MAX_N = 100, MAX_M = 100, MAX_K = 500;
int r[MAX_K], c[MAX_K], s[MAX_K], t[MAX_K];   // 第 i 隻魔王的位置與移動向量
bool alive[MAX_K];
bool bomb[MAX_N][MAX_M];       // 這格有沒有炸彈
bool exploded[MAX_N][MAX_M];   // 這一回合被引爆的格子

int main() {
    int n, m, k;
    cin >> n >> m >> k;
    for (int i = 0; i < k; i++) {
        cin >> r[i] >> c[i] >> s[i] >> t[i];
        alive[i] = true;
    }

    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:出界的消失;踩到炸彈的消失,並記下要清掉的格子
        int clear_r[MAX_K], clear_c[MAX_K];    // 要清掉的格子:列、欄各一個陣列
        int clear_count = 0;
        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;
                    clear_r[clear_count] = r[i];
                    clear_c[clear_count] = c[i];
                    clear_count++;
                }
            }
        }

        // 全部判定完才清炸彈:兩隻魔王同回合踩同一格,兩隻都要消失
        for (int i = 0; i < clear_count; i++) {
            int x = clear_r[i];
            int y = clear_c[i];
            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\) 列直接讀到棋盤外面。
  • 要清的格子用 clear_r、clear_c 兩個陣列記列和欄(clear_count 記收了幾格,語法書 6.7),exploded 表只是讓同一格不被記兩次;子題組版一維時把同一格清兩次也無妨,所以省了它。
  • \(k\) 隻魔王的資料用四個陣列平行存放,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),題目的範例解釋自己就在講這件事。
  • 出界只查行不查列(子題組版的習慣帶進完整版):兩個範例都會過(範例 2 的魔王走到第 \(6\) 列還沒超出陣列,放在棋盤外的炸彈也不會被數到);正式測資的魔王會一路走出陣列,讀寫到陣列外面——這是未定義行為,可能當掉、也可能悄悄算錯。