ZeroJudge 解題筆記：f928. 連環炸彈.................Boom！

作者：王一哲
日期：2025年10月29日


ZeroJudge 題目連結：f928. 連環炸彈.................Boom！

解題想法

這題的標籤是「遞迴」，不過我是用 BFS 解題。先讀取這格的炸彈種類 k，如果 k 等於 1 只會炸掉自己，如果 k 等於 2 再檢查左右兩格，如果 k 等於 3 則檢查左、右兩側距離 k 及 2k 的格子。檢查過的格子如果有炸彈，將炸彈加入待走訪佇列 que，再將檢查過的格子改成 0。

Python 程式碼

使用時間約為 24 ms，記憶體約為 3.8 MB，通過測試。

from collections import deque

n = int(input())
bombs = list(map(int, input().split()))
que = deque([int(input())])
while que:
    x = que.popleft()
    k = bombs[x]  # 暫存這格的值
    bombs[x] = 0  # 將這格歸零
    if k == 2:  # 如果 k 等於 2，檢查左、右兩格是否出界、是否有炸彈
        if x-1 >= 0 and bombs[x-1] != 0: que.append(x-1)
        if x+1 < n and bombs[x+1] != 0: que.append(x+1)
    elif k >= 3:  # 如果 k 大於等於 3，檢查左、右四格是否出界、是否有炸彈
        if x-k >= 0 and bombs[x-k] != 0: que.append(x-k)
        if x-k-k >= 0 and bombs[x-k-k] != 0: que.append(x-k-k)
        if x+k < n and bombs[x+k] != 0: que.append(x+k)
        if x+k+k < n and bombs[x+k+k] != 0: que.append(x+k+k)
print(*bombs)

C++ 程式碼

使用時間約為 2 ms，記憶體約為 284 kB，通過測試。

#include <cstdio>
#include <queue>
using namespace std;

int main() {
    int n; scanf("%d", &n);
    int bombs[n];
    for(int i=0; i<n; i++) scanf("%d", &bombs[i]);
    queue<int> que;
    int x; scanf("%d", &x); que.push(x);
    while(!que.empty()) {
        x = que.front(); que.pop();
        int k = bombs[x];  // 暫存這格的值
        bombs[x] = 0;  // 將這格歸零
        if (k == 2) {  // 如果 k 等於 2，檢查左、右兩格是否出界、是否有炸彈
            if (x-1 >= 0 && bombs[x-1] != 0) que.push(x-1);
            if (x+1 < n && bombs[x+1] != 0) que.push(x+1);
        } else if (k >= 3) {  // 如果 k 大於等於 3，檢查左、右四格是否出界、是否有炸彈
            if (x-k >= 0 && bombs[x-k] != 0) que.push(x-k);
            if (x-k-k >= 0 && bombs[x-k-k] != 0) que.push(x-k-k);
            if (x+k < n && bombs[x+k] != 0) que.push(x+k);
            if (x+k+k < n && bombs[x+k+k] != 0) que.push(x+k+k);
        }
    }
    for(int i=0; i<n-1; i++) printf("%d ", bombs[i]);
    printf("%d\n", bombs[n-1]);
    return 0;
}