o713.
3. 連鎖反應
內容
在一個 M x N 的網格中，每一格可能是石頭或是炸彈，具體包含以下數字：
-1表示石頭，無法被炸彈引爆，炸彈震波無法通過該格傳遞。-2表示初始炸彈的起始點，可以設定爆炸半徑。- 其他整數表示該位置存在爆炸半徑為該數值的炸彈。
炸彈爆炸時，會影響周圍一定範圍內的格子。炸彈會以該格為中心擴散，若一個炸彈的爆炸半徑為 $v$，則會將從該格開始沿著上、下、左或右走 $v$ 步內可以走到的格子都引爆。若某一顆炸彈引爆的範圍中涵蓋到尚未引爆的炸彈，則會引發鏈鎖反應將尚未引爆的炸彈引爆，並依循著相同的規則發生鏈鎖反應。
目標是找出初始炸彈所需設置的最小爆炸半徑，使得至少有 $q$ 個格子被引爆。
輸入說明
第一行有三個正整數 $M, N, q (2 \le M, N \le 500, 1 < q \le M \times N)$，接下來有 $M$ 行，每一行有 $N$ 個數字。保證炸彈半徑為正數的數量最多只有 $1500$ 個，且在場上的炸彈半徑不超過 $30$。
保證一定存在一個初始炸彈的爆炸半徑使得引爆的格子數量至少 $q$。
(20%): $1 \le M, N \le 100$，炸彈半徑為正的數量不超過 $100$ 且場上沒有任何石頭。
(40%): $1 \le M, N \le 200$，炸彈半徑為正的數量不超過 $200$，場上的炸彈半徑不超過 $20$。
(40%): 無限制
輸出說明
輸出至少需要設置爆炸半徑多大的炸彈，才能使得至少有 $q$ 個格子被引爆。
範例輸入
#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
測資資訊：
記憶體限制：
256
MB
提示 ：
範例輸入1
若於 $(2, 0)$ 處設置爆炸半徑 $3$，第一次引爆的範圍如下紅色底色範圍。
由於 $(0, 1)$ 處有一個炸彈，產生鏈鎖反應將該炸彈引爆。引爆範圍如下圖橘色處。
總共引爆 $11$ 個格子。
標籤:
出處:
2024年10月APCS
[管理者：
algo.seacow@
...
(演算法海牛)
]
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
| 44474 |
|
o713 | 57 | 2024-12-08 23:10 | |
| 43727 |
|
o713 | 1862 | 2024-10-24 22:43 | |
| 43512 |
|
o713 | 1992 | 2024-10-21 01:49 |