a326. 3. 連鎖反應

Content

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

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

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

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

Input

第一行有三個正整數 $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%): 無限制

Output

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

Sample Input #1

Sample Output #1

Sample Input #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

Sample Output #2

測資資訊：

記憶體限制： 256 MB
公開測資點#0 (5%): 1.0s , <1M
公開測資點#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.5s , <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

Hint ：

範例輸入1

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

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

總共引爆 $11$ 個格子。

Tags:

出處:

2024年10月 APCS [管理者： ktlai(測試員) ]

ID	User	Problem	Subject	Hit	Post Date
沒有發現任何「解題報告」