###### tags: `APCS`
# **f149－炸彈偵測器**
### **題目連結：** [**f149**](https://zerojudge.tw/ShowProblem?problemid=f149)
### **題目解析**
在這個問題中，我們有一個軍事基地正在開發的炸彈偵測器系統。這些偵測器會被放置在一個由R行和C列組成的矩陣中，並以中心位置為中心來檢測周圍的炸彈。偵測器相鄰的格子（八個方向）中如果有其他偵測器存在，則會發生磁場干擾，導致偵測器失靈。需要計算有多少炸彈可以被偵測到，以及有多少炸彈無法被偵測到。
### **解題方向**
1. 讀取輸入：
* 第一行包含兩個整數R和C，表示矩陣的行數和列數。
* 接下來的R行，每行有C個整數，表示矩陣中每個位置的狀態：5表示偵測器，1表示炸彈，0表示空地。
1. 檢查偵測器：
* 對於每一個位置，如果是偵測器5，則檢查它周圍的八個格子是否有其他偵測器。如果有，則將該偵測器設為失靈6。
* 如果偵測器周圍沒有其他偵測器，它可以有效工作，檢查周圍是否有炸彈，若有炸彈則計數偵測到的炸彈。
1. 計算結果：
* 最後遍歷矩陣，計算未被偵測到的炸彈數量。
### **程式解析**
導入模組與函數定義
```python
import sys
def showmap(m, r, c):
for i in range(0, r):
for j in range(0, c):
print(m[i][j], end=' ')
print()
```
* import sys: 導入sys模組以使用標準輸入。
* showmap 函數：這個函數用於打印地圖的當前狀態，接受一個二維列表m和它的行數r與列數c。雖然這個函數在當前程式碼中被註釋掉並未使用，但它對於除錯或顯示地圖狀態很有用。
讀取輸入和初始化地圖
```python
# 讀取行數和列數
s = input()
size = [int(i) for i in s.split()]
R = size[0]
C = size[1]
# 初始化地圖矩陣
MAP = []
# 讀取地圖
r = 0
for s in sys.stdin:
row = list(map(int, s.split()))
MAP.append(row)
r += 1
if r >= R:
break
```
* 讀取行數和列數：
* 使用input()讀取第一行的R和C，表示地圖的行數和列數。
* size = [int(i) for i in s.split()]將讀入的字串分割為整數列表。
* R和C分別表示地圖的行和列。
* 初始化地圖：
* MAP = [] 初始化一個空列表來存儲地圖。
* 讀取地圖內容：使用sys.stdin來讀取後續的R行數據，每行分割成整數並附加到MAP中。
* 用for迴圈和sys.stdin來逐行讀取地圖的每一行，直到讀完R行。
初始化偵測器和炸彈計數
```python
detected = 0
undetected = 0
```
檢查偵測器的有效性
```python
# 檢查地圖以偵測炸彈
for i in range(0, R):
for j in range(0, C):
# 檢查是否為偵測器
if MAP[i][j] != 0 and MAP[i][j] != 1:
# 檢查周圍八個方向
for m in range(j-1, j+2):
for n in range(i-1, i+2):
if m >= 0 and m < C and n >= 0 and n < R and not (m == j and n == i):
if MAP[n][m] >= 5: # 發現相鄰偵測器
MAP[n][m] = 6 # 標記為失靈
MAP[i][j] = 6
```
* 雙重迴圈遍歷整個矩陣：
* 外層迴圈for i in range(0, R) 遍歷每一行。
* 內層迴圈for j in range(0, C) 遍歷每一列。
* 檢查偵測器：
* 如果地圖上位置MAP[i][j]的值不是0（空地）或1（炸彈），即為偵測器。
* 檢查偵測器周圍：
* 檢查偵測器周圍的八個格子（用m和n進行偏移）。
* 如果發現其他偵測器（值為5或以上），將當前偵測器標記為失靈6。
* MAP[n][m] = 6將相鄰的偵測器也標記為失靈。
偵測炸彈
```python
if MAP[i][j] == 5: # 如果偵測器沒失靈
for m in range(j-1, j+2):
for n in range(i-1, i+2):
if m >= 0 and m < C and n >= 0 and n < R:
if MAP[n][m] == 1: # 偵測到炸彈
detected += 1
MAP[n][m] = 0 # 標記炸彈為已偵測
```
* 檢查有效偵測器：
* 如果偵測器MAP[i][j]仍然為5（即沒有失靈），則它是有效的。
* 檢測炸彈：
* 再次檢查周圍的八個格子。
* 如果發現炸彈（MAP[n][m] == 1），則計數偵測到的炸彈，並將炸彈位置標記為0，表示已被偵測。
計算未偵測炸彈
```python
# 計算未被偵測到的炸彈數量
for i in range(0, R):
for j in range(0, C):
if MAP[i][j] == 1:
undetected += 1
```
* 遍歷整個地圖：
* 再次使用雙重迴圈遍歷矩陣。
* 計算未偵測到的炸彈：
* 如果位置MAP[i][j]仍然是1，表示該炸彈未被偵測，將undetected計數加一。
### **完整程式碼**
```python=
import sys
def showmap(m, r, c):
for i in range(0, r):
for j in range(0, c):
print(m[i][j], end=' ')
print()
#start
s = input()
size = [ int(i) for i in s.split() ]
R = size[0]
C = size[1]
MAP = []
r = 0
for s in sys.stdin: # 把資料丟入list
row = list(map(int, s.split()))
MAP.append(row)
r +=1
if r >= R :
break
#showmap(MAP, R, C)
detected = 0
undetected = 0
#detect mine
for i in range(0, R):
for j in range(0, C):
# check map
if MAP[i][j] != 0 and MAP[i][j] != 1:
# * * *
# * 5 *
# * * *
for m in range(j-1, (j+1)+1):# 偵測附近八個點是否有「其他偵測器」
for n in range(i-1, (i+1)+1):
if m>=0 and m<C and n>=0 and n<R and not (m==j and n==i):
# 確保在界限之內，且會跳過MAP[i][j]
if MAP[n][m] >=5:
#print("find...", n, m)
#當偵測器的範圍內包含另一個偵測器時（即，當周圍的八個點中至少有一點的值大於或等於 5），當前的偵測器（MAP[i][j]）和該範圍內的其他偵測器的值都會被設置為 6。這代表兩個或多個偵測器之間的信號干擾，導致它們無法正常偵測炸彈。
MAP[n][m] = 6
MAP[i][j] = 6
if MAP[i][j] == 5:# MAP[i][j]還是5就代表範圍內沒有其他偵測器
#print("find detector in ", i, j)
# 偵測附近八個點是否有炸彈
for m in range(j-1, (j+1)+1):# 慢慢將偵測到的累加起來
for n in range(i-1, (i+1)+1):
if m>=0 and m<C and n>=0 and n<R:
if MAP[n][m] == 1:
detected += 1
MAP[n][m] = 0 # 偵測到炸彈後將1改為0
# end of if
#showmap(MAP, R, C)
for i in range(0, R):
for j in range(0, C):
if MAP[i][j] == 1:# 已偵測的為0，未偵測的就是原來的1
undetected += 1
#showmap(MAP, R, C)
print(detected, undetected)
```
Sign in with Wallet
Connect another wallet