# APCS實作題2024年10月第3題：連鎖反應

> 日期：2024年10月31日
> 作者：王一哲
> [ZeroJudge 題目連結](https://zerojudge.tw/ShowProblem?problemid=o713)

<br />

## 題目

### 問題描述

在一個 $M \times N$ 的網格中，每一格可能是石頭或是炸彈，具體包含以下數字：

- $-1$ 表示石頭，無法被炸彈引爆，炸彈震波無法通過該格傳遞。
- $-2$ 表示初始炸彈的起始點，可以設定爆炸半徑。
- 其他整數表示該位置存在爆炸半徑為該數值的炸彈。

炸彈爆炸時，會影響周圍一定範圍內的格子。炸彈會以該格為中心擴散，若一個炸彈的爆炸半徑為 $v$，則會將從該格開始沿著上、下、左或右走 $v$ 步內可以走到的格子都引爆。若某一顆炸彈引爆的範圍中涵蓋到尚未引爆的炸彈，則會引發鏈鎖反應將尚未引爆的炸彈引爆，並依循著相同的規則發生鏈鎖反應。

目標是找出初始炸彈所需設置的最小爆炸半徑，使得至少有 $q$ 個格子被引爆。
<br />

### 輸入格式

第一行有三個正整數 $M, N, q ~(2 \leq M, N \leq 500,~1 < q \leq M, N)$，接下來有 $M$ 行，每一行有 $N$ 個數字。保證炸彈半徑為正數的數量最多只有 $1500$ 個，且在場上的炸彈半徑不超過 $30$。

保證一定存在一個初始炸彈的爆炸半徑使得引爆的格子數量至少 $q$。

子題配分
- 20%：$1 \leq M, N \leq 100$，炸彈半徑為正的數量不超過 $100$ 且場上沒有任何石頭。
- 40%：$1 \leq M, N \leq 200$，炸彈半徑為正的數量不超過 $200$，場上的炸彈半徑不超過 $20$。
- 40%：無限制
<br />

### 輸出格式

輸出至少需要設置爆炸半徑多大的炸彈，才能使得至少有 $q$ 個格子被引爆。
<br />

### 範例輸入1

3 5 10
0 2 0 0 1
0 0 0 1 0
-2 0 0 0 0

### 範例輸出1

3

### 範例輸入2

4 6 10
0 0 -1 -1 -1 0
0 0 -1 1 -1 2
0 -1 0 -1 0 0
2 -2 0 0 0 -1

### 範例輸出2

4

<br />

## Python 程式碼

第6筆測資開始超時。

M, N, q = map(int, input().split())  # 地圖列數 M、欄數 N，目標格數 q
grid = []  # 地圖
r0, c0 = 0, 0  # 放入炸彈位置預設值
for i in range(M):  # 讀取 M 行資料
    g = list(map(int, input().split()))  # 讀取一行資料
    grid.append(g)  # 將 g 加入 grid
    if -2 in g:  # 如果 g 之中有 -2，找到放入炸彈
        r0 = i; c0 = g.index(-2)  # 更新 (r0, c0)

def bfs(R0):  # 代入放置炸彈的爆炸半徑 R0
    if q == 1: return True  # 例外狀況，q 等於 1，一定成立，直接回傳 True
    que = [(r0, c0, R0)]  # 要搜尋的佇列
    head = 0  # 由 que 讀取資料的索引值
    count = 1  # 放炸彈的位置一定會炸掉，至少有 1 格
    visited = [[0]*N for _ in range(M)]  # 走訪狀態，若已走訪，存入炸彈於此格剩下的爆炸格數加 30
    visited[r0][c0] = R0 + 30  # 起點已走訪
    while head < len(que):  # 如果 head 還沒有出界繼續執行
        r, c, R = que[head]; head += 1  # 由 que 讀取資料並更新 head
        if R == 0: continue  # 如果已經不會再向外延伸，找下一筆資料        
        for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)):  # 四方向搜尋
            nr, nc = r + dr, c + dc  # 要檢驗的位置 (nr, nc)
            if nr < 0 or nr >= M or nc < 0 or nc >= N or grid[nr][nc] == -1:
                continue  # 出界或遇到石頭，找下一個位置
            nR = max(grid[nr][nc], R-1)  # 下次檢測時剩下的爆炸格數，取新炸彈的爆炸半徑及 R-1 較大者
            if nR > visited[nr][nc] - 30:  # 這次檢測時爆炸範圍大於前一次檢測結果
                if visited[nr][nc] == 0: count += 1  # 此格還沒有炸過，count 加 1
                visited[nr][nc] = nR + 30  # 已走訪
                que.append((nr, nc, nR))  # 更新 que
        if count >= q: return True  # 如果 count 大於等於 q，回傳 True
    # end of while loop
    return False  # 已走訪完時已爆炸格數小於 q，回傳 False

low, high, ans = 0, 5000, 0  # 放置炸彈爆炸半徑最小值 0、最大值，答案先預設為 0
while high >= low:  # 二分搜尋法
    mid = (high - low) // 2 + low  # 求中間值
    if bfs(mid):
        ans = mid; high = mid-1
    else:
        low = mid+1
# end of while loop
print(ans)

<br /><br />

改用 collections.deque 儲存要走訪的資料，第6筆測資開始超時。

from collections import deque

M, N, q = map(int, input().split())  # 地圖列數 M、欄數 N，目標格數 q
grid = []  # 地圖
r0, c0 = 0, 0  # 放入炸彈位置預設值
for i in range(M):  # 讀取 M 行資料
    g = list(map(int, input().split()))  # 讀取一行資料
    grid.append(g)  # 將 g 加入 grid
    if -2 in g:  # 如果 g 之中有 -2，找到放入炸彈
        r0 = i; c0 = g.index(-2)  # 更新 (r0, c0)

def bfs(R0):  # 代入放置炸彈的爆炸半徑 R0
    if q == 1: return True  # 例外狀況，q 等於 1，一定成立，直接回傳 True
    que = deque([(r0, c0, R0)])  # 要搜尋的佇列
    count = 1  # 放炸彈的位置一定會炸掉，至少有 1 格
    visited = [[0]*N for _ in range(M)]  # 走訪狀態，若已走訪，存入炸彈於此格剩下的爆炸格數加 30
    visited[r0][c0] = R0 + 30  # 起點已走訪
    while que:  # 如果 que 還有資料繼續執行
        r, c, R = que.popleft()  # 由 q 開頭讀取並移除資料
        if R == 0: continue  # 如果已經不會再向外延伸，找下一筆資料        
        for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)):  # 四方向搜尋
            nr, nc = r + dr, c + dc  # 要檢驗的位置 (nr, nc)
            if nr < 0 or nr >= M or nc < 0 or nc >= N or grid[nr][nc] == -1:
                continue  # 出界或遇到石頭，找下一個位置
            nR = max(grid[nr][nc], R-1)  # 下次檢測時剩下的爆炸格數，取新炸彈的爆炸半徑及 R-1 較大者
            if nR > visited[nr][nc] - 30:  # 這次檢測時爆炸範圍大於前一次檢測結果
                if visited[nr][nc] == 0: count += 1  # 此格還沒有炸過，count 加 1
                visited[nr][nc] = nR + 30  # 已走訪
                que.append((nr, nc, nR))  # 更新 que
        if count >= q: return True  # 如果 count 大於等於 q，回傳 True
    # end of while loop
    return False  # 已走訪完時已爆炸格數小於 q，回傳 False

low, high, ans = 0, 5000, 0  # 放置炸彈爆炸半徑最小值 0、最大值，答案先預設為 0
while high >= low:  # 二分搜尋法
    mid = (high - low) // 2 + low  # 求中間值
    if bfs(mid):
        ans = mid; high = mid-1
    else:
        low = mid+1
# end of while loop
print(ans)

<br /><br />

## C++ 程式碼

費時最久約 0.3 s，使用記憶體最多 113.4 MB，通過測試。

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

int M, N, q, r0, c0;  // 地圖列數 M、欄數 N，目標格數 q，放入炸彈位置預設值
vector<vector<int>> grid (500, vector<int> (500));  // 地圖，在 main 之中 resize
int dr[4] = {0, 1, 0, -1}, dc[4] = {1, 0, -1, 0};  // 四方向搜尋用的陣列

bool bfs(int R0) {  // 代入放置炸彈的爆炸半徑 R0
    if (q == 1) return true;  // 例外狀況，q 等於 1，一定成立，直接回傳 true
    vector<vector<int>> que = {{r0, c0, R0}};  // 要搜尋的佇列
    size_t head = 0;  // 由 que 讀取資料的索引值
    int count = 1;  // 放炸彈的位置一定會炸掉，至少有 1 格
    vector<vector<int>> visited (M, vector<int> (N, 0));  // 走訪狀態，若已走訪，存入炸彈於此格剩下的爆炸格數加 30
    visited[r0][c0] = R0 + 30;  // 起點已走訪
    while(head < que.size()) {  // 如果 head 還沒有出界繼續執行
        int r = que[head][0], c = que[head][1], R = que[head][2]; head++;  // 由 que 讀取資料並更新 head
        if (R == 0) continue;  // 如果已經不會再向外延伸，找下一筆資料        
        for(int i=0; i<4; i++) {  //  四方向搜尋
            int nr = r + dr[i], nc = c + dc[i];  // 要檢驗的位置 (nr, nc)
            if (nr < 0 || nr >= M || nc < 0 || nc >= N || grid[nr][nc] == -1) continue;  // 出界或遇到石頭，找下一個位置
            int nR = max(grid[nr][nc], R-1);  // 下次檢測時剩下的爆炸格數，取新炸彈的爆炸半徑及 R-1 較大者
            if (nR > visited[nr][nc] - 30) {  // 這次檢測時爆炸範圍大於前一次檢測結果
                if (visited[nr][nc] == 0) count++;  // 此格還沒有炸過，count 加 1
                visited[nr][nc] = nR + 30;  // 已走訪
                que.push_back({nr, nc, nR});  // 更新 que
            }
        }
        if (count >= q) return true;  // 如果 count 大於等於 q，回傳 true
    }
    return false;  // 已走訪完時已爆炸格數小於 q，回傳 false
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> M >> N >> q;  // 讀取 M, N, q
    grid.resize(M);  // 更新 grid 的維度為 M*N
    for(int i=0; i<M; i++) grid[i].resize(N);
    for(int i=0; i<M; i++) {  // 讀取 M 行資料
        for(int j=0; j<N; j++) {
            int g; cin >> g;  // 讀取 N 個數字
            grid[i][j] = g;  // 更新 grid
            if (g == -2) {  // 找到放入炸彈位置
                r0 = i; c0 = j;  // 更新 (r0, c0)
            }
        }
    }

    int low = 0, high = M*N, ans = 0;  // 放置炸彈爆炸半徑最小值 0、最大值，答案先預設為 0
    while(high >= low) {  // 二分搜尋法
        int mid = (high - low) / 2 + low;  // 求中間值
        if (bfs(mid)) {
            ans = mid; high = mid-1;
        } else {
            low = mid+1;
        }
    }
    cout << ans << "\n";
    return 0;
}

<br /><br />

改用 queue 儲存要走訪的資料，費時最久約 0.2 s，使用記憶體最多 16.7 MB，通過測試。

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

int M, N, q, r0, c0;  // 地圖列數 M、欄數 N，目標格數 q，放入炸彈位置預設值
vector<vector<int>> grid (500, vector<int> (500));  // 地圖，在 main 之中 resize
int dr[4] = {0, 1, 0, -1}, dc[4] = {1, 0, -1, 0};  // 四方向搜尋用的陣列

bool bfs(int R0) {  // 代入放置炸彈的爆炸半徑 R0
    if (q == 1) return true;  // 例外狀況，q 等於 1，一定成立，直接回傳 true
    queue<vector<int>> que; que.push({r0, c0, R0});  // 要搜尋的佇列
    int count = 1;  // 放炸彈的位置一定會炸掉，至少有 1 格
    vector<vector<int>> visited (M, vector<int> (N, 0));  // 走訪狀態，若已走訪，存入炸彈於此格剩下的爆炸格數加 30
    visited[r0][c0] = R0 + 30;  // 起點已走訪
    while(!que.empty()) {  // 如果 que 還有資料繼續執行
        int r = que.front()[0], c = que.front()[1], R = que.front()[2]; que.pop();  // 由 que 開頭讀取並移除資料
        if (R == 0) continue;  // 如果已經不會再向外延伸，找下一筆資料        
        for(int i=0; i<4; i++) {  //  四方向搜尋
            int nr = r + dr[i], nc = c + dc[i];  // 要檢驗的位置 (nr, nc)
            if (nr < 0 || nr >= M || nc < 0 || nc >= N || grid[nr][nc] == -1) continue;  // 出界或遇到石頭，找下一個位置
            int nR = max(grid[nr][nc], R-1);  // 下次檢測時剩下的爆炸格數，取新炸彈的爆炸半徑及 R-1 較大者
            if (nR > visited[nr][nc] - 30) {  // 這次檢測時爆炸範圍大於前一次檢測結果
                if (visited[nr][nc] == 0) count++;  // 此格還沒有炸過，count 加 1
                visited[nr][nc] = nR + 30;  // 已走訪
                que.push({nr, nc, nR});  // 更新 que
            }
        }
        if (count >= q) return true;  // 如果 count 大於等於 q，回傳 true
    }
    return false;  // 已走訪完時已爆炸格數小於 q，回傳 false
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> M >> N >> q;  // 讀取 M, N, q
    grid.resize(M);  // 更新 grid 的維度為 M*N
    for(int i=0; i<M; i++) grid[i].resize(N);
    for(int i=0; i<M; i++) {  // 讀取 M 行資料
        for(int j=0; j<N; j++) {
            int g; cin >> g;  // 讀取 N 個數字
            grid[i][j] = g;  // 更新 grid
            if (g == -2) {  // 找到放入炸彈位置
                r0 = i; c0 = j;  // 更新 (r0, c0)
            }
        }
    }

    int low = 0, high = M*N, ans = 0;  // 放置炸彈爆炸半徑最小值 0、最大值，答案先預設為 0
    while(high >= low) {  // 二分搜尋法
        int mid = (high - low) / 2 + low;  // 求中間值
        if (bfs(mid)) {
            ans = mid; high = mid-1;
        } else {
            low = mid+1;
        }
    }
    cout << ans << "\n";
    return 0;
}

<br /><br />

---

###### tags:`APCS`、`Python`、`C++`