時間限制 1000 ms ・ 記憶體限制 256 MB
題目描述
M×N 方格中，−1 是不可穿越且不會被引爆的石頭，−2 是唯一的初始炸彈，其半徑由你決定；其餘非負整數為該格炸彈的半徑。炸彈爆炸後，以該格為起點，沿上下左右且避開石頭，在半徑步數內能抵達的格子都會被引爆，起點本身也計入。被波及但尚未爆炸的炸彈會接著以自己的半徑引爆，直到沒有新反應。求初始半徑的最小值，讓至少 Q 個不同格子被引爆。
輸入格式
第一行為 M、N、Q，2 ≤ M,N ≤ 500，1 < Q ≤ M×N。接著 M 行各有 N 個格子值。半徑為正的炸彈最多 1500 顆，既有炸彈半徑不超過 30；保證有解。
輸出格式
輸出初始炸彈所需的最小爆炸半徑。
範例測資
範例輸入 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
請先登入後再提交程式碼
討論與題解
載入討論區…