ETH官方钱包

切換
舊版
前往
大廳
主題

ZeroJudge - f149: 3. 炸彈偵測器 (Detector) 解題心得

Not In My Back Yard | 2020-07-12 00:32:23 | 巴幣 2 | 人氣 677

題目連結:


題目大意:
輸入第一列給定兩正整數 R 、 C (1 ≦ R 、C ≦ 15),代表有一個 R 列 C 行的地圖網格。接著有 R 列,每列給定 C 個數字,代表地圖每個格子之內容。數字只會是 0 、 1 、 5 其中一者,依序代表空地、炸彈以及炸彈偵測器。

炸彈偵測器可以偵測到其周遭八格(左上、上、右上、右、右下、下、左下、左以及左上的格子)的炸彈。但是當周遭八格有其他的炸彈偵測器時,訊號會彼此干擾,使得這些互相干擾的偵測器皆無法偵測炸彈。

給定地圖的內容,試問有多少炸彈會被偵測出來,並還有多少炸彈未被偵測出來?輸出格式參見輸出範例。



範例輸入:
輸入範例一:
3 3
0 0 0
0 5 0
0 1 0

輸入範例二:
3 3
5 0 0
5 1 5
0 0 5

輸入範例三:
4 4
5 0 0 0
0 1 1 0
0 0 0 5
5 1 0 0

輸入範例四:
5 5
0 0 0 0 0
1 5 1 0 0
0 0 0 5 0
1 5 1 0 0
0 0 0 0 0

輸入範例五:
10 10
0 1 5 0 0 0 0 0 0 0
5 0 0 0 1 5 0 0 0 0
1 0 0 0 0 0 0 0 5 0
0 0 1 0 0 0 0 5 0 0
0 0 5 0 5 0 1 0 0 0
0 0 0 0 1 0 5 0 0 0
0 1 5 0 5 0 0 0 1 5
0 0 0 1 0 0 0 0 0 0
1 0 0 5 5 1 0 0 0 0
5 0 0 0 0 0 0 1 5 0


範例輸出:
輸出範例一:
1 0

輸出範例二:
0 1

輸出範例三:
3 0

輸出範例四:
4 0

輸出範例五:
11 1


解題思維:
先掃一次地圖,將每個偵測器的周遭八格都設為「被干擾」,並用一個二維陣列表示這 R × C 的位置各自有無被干擾。然後順便統計炸彈的總個數。

然後接著看每個偵測器,該偵測器是不是處於被干擾的位置。如果沒有,就看看周遭八格有沒有炸彈,有的話,偵測的炸彈數就 + 1 。

最後輸出偵測炸彈數,然後將總炸彈數減去偵測到的數量即是未被偵測到的那些炸彈之數目。

此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。
追蹤 創作集

作者相關創作

相關創作

更多創作