ZeroJudge 解題筆記：n700. 蝸牛的踩地雷攻略 3 (點方塊)

作者：王一哲
日期：2025年12月12日


ZeroJudge 題目連結：n700. 蝸牛的踩地雷攻略 3 (點方塊)

解題想法

為了不要檢查是否出界，我習慣在地圖的最右側、最下方加上用不到的符號當作哨兵。用自訂函式 count 計算周圍 8 格的地雷數量，再用另一個自訂函式 reveal 翻開格子，reveal 之中是用 BFS 找出所有可以翻開的格子，同時將翻開後的地圖儲存到另一個二維串列之中。

Python 程式碼

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

from collections import deque

def count(grid, r, c):  # 計算周圍 8 格的地雷數量
    cnt = 0  # 地雷數量
    for dr, dc in ((0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1), (-1, 0), (-1, 1)):
        nr, nc = r+dr, c+dc
        if grid[nr][nc] == '*': cnt += 1
    return cnt

def reveal(grid, result, ri, ci, n, m):  # 翻開格子，代入地圖 grid，結果 result，位置 (ri, ci)，維度 n*m
    visited = [[False]*(m+1) for _ in range(n+1)]  # 是否已走訪
    que = deque([(ri, ci)])  # 待走訪的位置
    visited[ri][ci] = True  # (ri, ci) 已走訪
    while que:  # 如果 que 還有資料繼續執行
        r, c = que.popleft()  # 從 que 開頭讀取並移除資料
        cnt = count(grid, r, c)  # 計算 (r, c) 周圍的地雷數量
        if cnt == 0:  # 如果周圍沒有地雷
            result[r][c] = '_'  # 翻開，是空地
            # 檢查周圍 8 格，如果還沒有出界、沒有走訪、是未翻開的格子
            for dr, dc in ((0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1), (-1, 0), (-1, 1)):
                nr, nc = r+dr, c+dc
                if grid[nr][nc] != '@' and not visited[nr][nc] and grid[nr][nc] == '#':
                    visited[nr][nc] = True  # (nr, nc) 已走訪
                    que.append((nr, nc))  # (nr, nc) 加入 que
        else: result[r][c] = str(cnt)  # 周圍有地雷，填入地雷的數量

def main():  # 主程式
    n, m, ri, ci = map(int, input().split())  # 地圖維度 n*m，起點 (ri, ci)
    grid = [list(input().strip() + '@') for _ in range(n)]  # 最右側加上 @ 作為哨兵
    grid.append(['@']*(m+1))  # 最下方加 m+1 個 @ 作為哨兵
    result = [['#']*m for _ in range(n)]  # 儲存結果用的 n*m 二維串列
    ri -= 1; ci -= 1  # 配合索引值，ri, ci 減 1
    reveal(grid, result, ri, ci, n, m)  # 呼叫 reveal 求解
    for row in result: print("".join(row))  # 印出答案

if __name__ == '__main__':
    main()

C++ 程式碼

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

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

int count(vector<string>& grid, int r, int c) {
    int dr[8] = {0, 1, 1, 1, 0, -1, -1, -1}, dc[8] = {1, 1, 0, -1, -1, -1, 0, 1}, cnt = 0;
    for(int i=0; i<8; i++) {
        int nr = r+dr[i], nc = c+dc[i];
        if (grid[nr][nc] == '*') cnt++;
    }
    return cnt;
}

void reveal(vector<string>& grid, vector<string>& result, int ri, int ci) {
    size_t gn = grid.size(), gm = grid[0].size();
    vector<vector<bool>> visited (gn, vector<bool> (gm, false));
    queue<pair<int, int>> que;
    que.push(make_pair(ri, ci));
    visited[ri][ci] = true;
    int dr[8] = {0, 1, 1, 1, 0, -1, -1, -1}, dc[8] = {1, 1, 0, -1, -1, -1, 0, 1};
    while(!que.empty()) {
        int r = que.front().first, c = que.front().second;
        que.pop();
        int cnt = count(grid, r, c);
        if (cnt == 0) {
            result[r][c] = '_';
            for(int i=0; i<8; i++) {
                int nr = r+dr[i], nc = c+dc[i];
                if (grid[nr][nc] != '@' && !visited[nr][nc] && grid[nr][nc] == '#') {
                    visited[nr][nc] = true;
                    que.push(make_pair(nr, nc));
                }
            }
        } else {
            result[r][c] = char(cnt+'0');
        }
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m, ri, ci; cin >> n >> m >> ri >> ci;
    vector<string> grid (n+2);
    string sentry (m+2, '@');
    grid[0] = sentry;
    grid[n+1] = sentry;
    for(int i=1; i<=n; i++) {
        string s; cin >> s;
        grid[i] = "@" + s + "@";
    }
    string space (m+2, '#');
    vector<string> result (n+2, space);
    reveal(grid, result, ri, ci);
    for(int i=1; i<=n; i++) {
        cout << result[i].substr(1, m) << "\n";
    }
    return 0;
}