ZeroJudge 解題筆記：c231.踩地雷

作者：王一哲
日期：2026年11月14日


ZeroJudge 題目連結：c231.踩地雷

解題想法

每組測資第一列為 3 個整數 $a, b, n$，$a, b$ 代表地圖大小為 $a \times b$，$n$ 代表有地雷數量。接下來 $n$ 列每列有 2 個整數 $row_i, col_i ~(1 \leq row_i, col_i \leq 10^4)$，代表第 $i$ 個地雷的位置。每個地雷周圍 8 格有感測器，如果某一個地雷爆炸時，周圍 8 格之中有其它地雷的感測器，則這些地雷會跟著被引爆。如果要用誘導彈引爆所有的地雷，至少需要幾個誘導彈？

這題我用 BFS 處理。先將地雷的坐標存入串列 $mines$，將感測器坐標對應的地雷編號存入字典 $sensors$，key 值為 tuple 格式的坐標 $(r, c)$，value 為串列格式。另外用一個 set 或陣列 $rem$ 記錄目前未被引爆的地雷編號。用一個 for 迴圈依序讀取地雷編號，如果遇到還沒有被引爆的地雷，答案 $ans + 1$，將這個地雷編號加入待走訪佇列 $que$，用 BFS 跑完所有會連鎖反應的地雷。這個寫法有點慢，但是比較容易理解。

Python 程式碼

使用時間約為 0.2 s，記憶體約為 42 MB，通過測試。

def solve():
    import sys
    from collections import deque

    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        a = int(data[ptr])  # 地圖 a 列
        b = int(data[ptr + 1])  # b 欄
        n = int(data[ptr + 2])  # n 個地雷
        ptr += 3

        mines = []  # 地雷坐標
        sensors = dict()  # 感測器坐標對應的地雷編號 (r, c): idx
        dr = (0, 1, 1, 1, 0, -1, -1, -1)  # 周圍 8 格的位移量
        dc = (1, 1, 0, -1, -1, -1, 0, 1)  # 周圍 8 格的位移量
        for i in range(n):
            r = int(data[ptr])
            c = int(data[ptr + 1])
            ptr += 2
            mines.append((r, c))
            for j in range(8):
                nr, nc = r + dr[j], c + dc[j]
                if (nr, nc) not in sensors:
                    sensors[nr, nc] = [i]
                else:
                    sensors[nr, nc].append(i)
        
        ans = 0  # 答案
        rem = set(range(n))  # 剩下的地雷
        for i in range(n):
            if i in rem:
                rem.remove(i)
                ans += 1
                # 測試周圍 8 格是否有其它未爆地雷的感測器
                que = deque([i])
                while que:
                    r, c = mines[que.popleft()]
                    for j in range(8):
                        nr, nc = r + dr[j], c + dc[j]
                        for k in sensors[nr, nc]:
                            if k in rem:
                                rem.remove(k)
                                que.append(k)
        result.append(f"{ans:d}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

C++ 程式碼

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

#include <iostream>
#include <vector>
#include <utility>
#include <map>
#include <queue>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int a, b, n;  // 地圖 a 列、b 欄，n 個地雷
    while(cin >> a >> b >> n) {
        vector<pair<int, int>> mines (n);  // 地雷坐標
        map<pair<int, int>, vector<int>> sensors;  // 感測器坐標對應的地雷編號 (r, c): idx
        int dr[8] = {0, 1, 1, 1, 0, -1, -1, -1};  // 周圍 8 格的位移量
        int dc[8] = {1, 1, 0, -1, -1, -1, 0, 1};  // 周圍 8 格的位移量
        for(int i = 0; i < n; i++) {
            int r, c;
            cin >> r >> c;
            mines[i] = make_pair(r, c);
            for(int j = 0; j < 8; j++) {
                int nr = r + dr[j], nc = c + dc[j];
                pair<int, int> pos = {nr, nc};
                sensors[pos].push_back(i);
            }
        }

        int ans = 0;  // 答案
        vector<bool> rem (n, true);  // 剩下的地雷
        for(int i = 0; i < n; i++) {
            if (rem[i]) {
                rem[i] = false;
                ans++;
                // 測試周圍 8 格是否有其它未爆地雷的感測器
                queue<int> que;
                que.push(i);
                while(!que.empty()) {
                    auto mine = mines[que.front()];
                    que.pop();
                    for(int j = 0; j < 8; j++) {
                        pair<int, int> nxt = {mine.first + dr[j], mine.second + dc[j]};
                        for(int k : sensors[nxt]) {
                            if (rem[k]) {
                                rem[k] = false;
                                que.push(k);
                            }
                        }
                    }
                }
            }
        }

        cout << ans << "\n";
    }
    return 0;
}