連鎖反應 (APCS 2024-10 中高級)

阿易哥接獲了一項尋寶任務，要潛入古老的遺跡中尋找寶藏。遺跡內部被設計為一個 \(M \times N\) 的二維陣列，每個元素 \((r, c)\) 對應在第 \(r\) 橫列第 \(c\) 直行的格子，其中橫列由上而下，直行由左往右，皆由 \(0\) 開始編號。為了防止偷盜，某些格子設置了陷阱，其他格子則是設有會阻擋訊號傳遞的石頭。一個陷阱一旦被觸發，會向四周傳遞訊號，讓周遭一定距離內的陷阱也一併被觸發，進而造成觸發陷阱的連鎖反應。

每個設有陷阱的格子都有一個非負整數，表示觸發該陷阱後之「影響半徑」；若該陷阱的影響半徑為 \(x\)，則距離該格子 \(x\) 步以內格子的陷阱也都會被觸發，其中距離的計算方式為：每一步可以向上、下、左或右走一格，但不能走到石頭所在的格子，也不能走到界外。若 \(x = 0\)，則表示該格子雖有陷阱，但它不會觸發其他格子的陷阱。目前除了寶藏所在位置的陷阱之外，其他格子的陷阱都已設置完畢，為了防止偷竊，當初遺跡設計者已在寶藏所在的位置設定陷阱之影響半徑（以下稱為初始半徑），預計一旦寶藏被竊時會觸發該陷阱，同時也能夠觸發至少 \(Q\) 個陷阱（包含寶藏所在位置的陷阱），請寫程式幫忙計算，寶藏位置的初始半徑最小值為多少。

舉例來說，下圖左的遺跡是一個 \(4 \times 5\) 的二維陣列的輸入，其中標示為 \(-2\) 的位置是寶藏，標示為 \(-1\) 的格子是石頭，訊號無法穿越，其他格子是陷阱，所標示的是該格子陷阱的影響範圍。假設初始半徑設為 \(0\)，則所能觸發的陷阱數量為 \(1\) 個，因為只有寶藏所在地的陷阱被觸發。假設初始半徑設為 \(1\)，如下圖右所示，則所能觸發的陷阱為 \(3\) 個，此時並無連鎖反應發生。

假設初始半徑設為 \(2\)，則一開始會觸發 \(7\) 個陷阱，如下圖左所示，但此時影響範圍內又有兩個半徑為 \(1\) 的陷阱被觸發。這兩個格子陷阱新觸發了 \(3\) 個陷阱，其中只有一個位於 \((0, 4)\) 的陷阱是影響半徑大於 \(0\) 的，最後，這個格子又觸發了位於 \((1, 4)\) 的陷阱。至此連鎖反應結束，被觸發的陷阱一共有 \(11\) 個。如果希望觸發的陷阱數量 \(Q = 10\)，則最小的初始半徑為 \(2\)。

輸入格式

輸入的第一行有 \(3\) 個整數 \(M\)、\(N\)、\(Q\)，\(2 \le M, N \le 500\)，\(1 < Q \le M \times N\)。接下來 \(M\) 行，每行有 \(N\) 個整數，為由上而下，由左而右每一個格子的值，若值為 \(-2\) 表示寶藏位置，若值為 \(-1\) 則表示該格子是石頭，否則是該格子的影響半徑。每個影響半徑是不超過 \(30\) 的非負整數，此外 \(K \le 1500\)，\(K\) 為影響半徑為正數的格子數量。寶藏所在的格子一定恰有一個，同一行兩個數值間以一個空白間隔。

輸出格式

一個整數，表示使得被觸發陷阱數量達到 \(Q\) 的最小初始半徑，答案必然存在。

範例輸入 1

4 6 19
0 0 0 0 0 0
0 1 1 0 0 0
0 0 0 -2 0 1
0 1 0 0 0 3

範例輸出 1

2

範例說明 1

初始半徑設為 \(2\) 時，觸發的陷阱如下圖。

範例輸入 2

4 5 10
9 -1 0 1 1
1 -1 -2 -1 1
0 1 0 0 -1
0 0 0 2 0

範例輸出 2

2

範例說明 2

此為題目中之範例。

評分說明

輸入包含若干筆測試資料，每一筆測試資料的執行時間限制均為 \(1\) 秒，Python 程式的執行時間限制為 \(4\) 秒，依正確通過測資筆數給分。其中：

• 第 1 子題組 20 分：\(M, N, K \le 100\)，且沒有石頭。
• 第 2 子題組 40 分：\(M, N \le 200\)，\(K \le 500\)，且除寶藏位置外的影響半徑均不超過 \(20\)。
• 第 3 子題組 40 分：無額外限制。

題目來源

APCS 程式實作中高級題本範例，程式實作 2024 年 10 月。