o713. 3. 連鎖反應 - 高中生程式解題系統

內容

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

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

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

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

輸入說明

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

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

(20%): $1 \leq M, N \leq 100$ ，炸彈半徑為正的數量不超過 $100$ 且場上沒有任何石頭。
(40%): $1 \leq M, N \leq 200$ ，炸彈半徑為正的數量不超過 $200$ ，場上的炸彈半徑不超過 $20$ 。
(40%): 無限制

輸出說明

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

範例輸入 #1

範例輸出 #1

範例輸入 #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

測資資訊：

記憶體限制： 256 MB
公開測資點#0 (5%): 1.0s , <1K
公開測資點#1 (5%): 1.0s , <1M
公開測資點#2 (5%): 1.0s , <1M
公開測資點#3 (5%): 1.0s , <1M
公開測資點#4 (5%): 1.0s , <1M
公開測資點#5 (5%): 1.0s , <1M
公開測資點#6 (5%): 1.0s , <1M
公開測資點#7 (5%): 1.0s , <1M
公開測資點#8 (5%): 1.0s , <1M
公開測資點#9 (5%): 1.0s , <1M
公開測資點#10 (5%): 1.0s , <1M
公開測資點#11 (5%): 1.0s , <1M
公開測資點#12 (5%): 1.0s , <1M
公開測資點#13 (5%): 1.0s , <1M
公開測資點#14 (5%): 1.0s , <1M
公開測資點#15 (5%): 1.0s , <1M
公開測資點#16 (5%): 1.0s , <1M
公開測資點#17 (5%): 1.0s , <1M
公開測資點#18 (5%): 1.0s , <1M
公開測資點#19 (5%): 1.0s , <1M

提示：

2025/1/29 更新：感謝 M_SQRT 協助加強測資

範例輸入1

若於 $(2, 0)$ 處設置爆炸半徑 $3$ ，第一次引爆的範圍如下紅色底色範圍。

由於 $(0, 1)$ 處有一個炸彈，產生鏈鎖反應將該炸彈引爆。引爆範圍如下圖橘色處。

總共引爆 $11$ 個格子。

標籤:

出處:

2024年10月 APCS [管理者： algo.seacow@gmail.com

algo.seacow@ ... (演算法海牛) ]

編號	身分	題目	主題	人氣	發表日期
44983	ray65155@gma ... (許晏睿)	o713	比較詳細的解析 & 答案	218	2024-12-31 16:27
45219	john1100729@ ... (靖諺)	o713	C++ 詳解(含第1~4題)	96	2025-01-26 22:07
44474	leeguanhan09 ... (李冠翰)	o713	Python 實作題1~4題詳解	203	2024-12-08 23:10
43727	samlin961112 ... (林哲甫)	o713	解題想法&C++答案&註解	2132	2024-10-24 22:43
43512	ericshen1955 ... (暴力又被TLE)	o713	不用二分搜	2188	2024-10-21 01:49