ZeroJudge 解題筆記：f149. 3. 炸彈偵測器 (Detector)

作者：王一哲
日期：2025年3月2日



ZeroJudge 題目連結：f149. 3. 炸彈偵測器 (Detector)

解題想法

因為在檢查周圍 8 格時可能會出界，造成 index error，所以我習慣在每列最後、最下面或四周加上 0。

Python 程式碼

使用時間約為 19 ms，記憶體約為 3.4 MB，通過測試。

m, n = map(int, input().split())  # 地圖 m*n
grid = [list(map(int, input().split())) + [0] for _ in range(m)]  # 地圖，結尾加上 0 作為哨兵
grid.append([0]*(n+1))  # 地圖最後加上 n+1 個 0 作為哨兵
bomb = set()  # 炸彈位置
found = set()  # 找到的炸彈位置
test = ((-1, -1), (-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1))  # 要檢測的周圍 8 格
for r in range(m):  # 依序掃過 r = 0 ~ m-1
    for c in range(n):  # 依序掃過 c = 0 ~ n-1
        if grid[r][c] == 1: bomb.add((r, c))  # 找到炸彈，(r, c) 加入 bomb
        elif grid[r][c] == 5:  # 偵測器
            other = False  # 周圍 8 格是否有其它的偵測器
            tmp = []  # 暫存周圍 8 格的炸彈位置
            for dr, dc in test:  # 依序檢測周圍 8 格
                nr, nc = r+dr, c+dc  # 要檢測的格子 (nr, nc)
                if grid[nr][nc] == 5:  # 其它的偵測器
                    other = True  # other 設定為 True
                    break  # 中止迴圈
                elif grid[nr][nc] == 1:  # 找到炸彈，(nr, nc) 加入 tmp
                    tmp.append((nr, nc))
            if not other:  # 如果周圍 8 格沒有其它的偵測器
                for (nr, nc) in tmp:  # 從 tmp 依序讀取找到的炸彈位置
                    found.add((nr, nc))  # (nr, nc) 加入 found
print(f"{len(found):d} {len(bomb)-len(found):d}")  # 印出答案

C++ 程式碼

使用時間約為 2 ms，記憶體約為 352 kB，通過測試。

#include <iostream>
#include <vector>
#include <set>
#include <utility>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int m, n; cin >> m >> n;  // 地圖 m*n
    vector<vector<int>> grid (m+2, vector<int> (n+2, 0));  // 地圖，四周加上 0 作為哨兵
    for(int r=1; r<=m; r++) {
        for(int c=1; c<=n; c++) {
            cin >> grid[r][c];
        }
    }
    set<pair<int, int>> bomb, found;  // 炸彈位置，找到的炸彈位置
    int test[8][2] = {{-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}};  // 要檢測的周圍 8 格
    for(int r=1; r<=m; r++) {  // 依序掃過 r = 1 ~ m
        for(int c=1; c<=n; c++) {  // 依序掃過 c = 1 ~ n
            if (grid[r][c] == 1) {
                bomb.insert(make_pair(r, c));  // 找到炸彈，(r, c) 加入 bomb
            } else if (grid[r][c] == 5) {  // 偵測器
                bool other = false;  // 周圍 8 格是否有其它的偵測器
                vector<pair<int, int>> tmp;  // 暫存周圍 8 格的炸彈位置
                for(int i=0; i<8; i++) {  // 依序檢測周圍 8 格
                    int nr = r + test[i][0], nc = c + test[i][1];  // 要檢測的格子 (nr, nc)
                    if (grid[nr][nc] == 5) {  // 其它的偵測器
                        other = true;  // other 設定為 True
                        break;  // 中止迴圈
                    } else if (grid[nr][nc] == 1) {  // 找到炸彈，(nr, nc) 加入 tmp
                        tmp.push_back(make_pair(nr, nc));
                    }
                }
                if (!other) {  // 如果周圍 8 格沒有其它的偵測器
                    for(auto pos : tmp) {  // 從 tmp 依序讀取找到的炸彈位置
                        found.insert(pos);  // pos 加入 found
                    }
                }
            }
        }
    }
    cout << found.size() << " " << bomb.size()-found.size() << "\n";  // 印出答案
    return 0;
}