ZeroJudge 解題筆記：k615. 蝸牛的踩地雷攻略 2 (掃雷)

作者：王一哲
日期：2025年11月30日


ZeroJudge 題目連結：k615. 蝸牛的踩地雷攻略 2 (掃雷)

解題想法

用二維串列儲存地圖，在最右側、最下方加上底線當作哨兵。接下來依序掃過地圖每一格，遇到不是數子的格子就跳過；計算周圍 8 格未翻開的格子數量 space 以及標記的數量 bomb，如果 space 大於 0 而且 bomb 等於這格的數字，則這格周圍的炸彈都已經被標記，這格改成 0。

Python 程式碼

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

n, m = map(int, input().split())
grid = [list(input() + '_') for _ in range(n)]
grid.append(['_']*(m+1))
for r in range(n):
    for c in range(m):
        if not grid[r][c].isnumeric(): continue
        bomb, space = 0, 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] == '#':
                space += 1
            elif grid[nr][nc] == 'P':
                bomb += 1
        if space > 0 and bomb == int(grid[r][c]):
            grid[r][c] = 'O'
for row in grid[:n]:
    print("".join(row[:m]))

C++ 程式碼

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

#include <cstdio>
#include <cctype>
#include <vector>
#include <utility>
using namespace std;
int main() {
    int n, m; scanf("%d %d", &n, &m);
    char grid[n+2][m+2];
    for(int c=0; c<m+2; c++) {
        grid[0][c] = '_';
        grid[n+1][c] = '_';
    }
    for(int r=1; r<=n; r++) {
        scanf("%s", grid[r]+1);
        grid[r][0] = '_';
        grid[r][m+1] = '_';
    }
    int dr[8] = {0, 1, 1, 1, 0, -1, -1, -1}, dc[8] = {1, 1, 0, -1, -1, -1, 0, 1};
    for(int r=1; r<=n; r++) {
        for(int c=1; c<=m; c++) {
            if (!isdigit(grid[r][c])) continue;
            int bomb = 0, space = 0;
            for(int i=0; i<8; i++) {
                int nr = r+dr[i], nc = c+dc[i];
                if (grid[nr][nc] == '#') space++;
                else if (grid[nr][nc] == 'P') bomb++;
            }
            if (space > 0 && bomb == grid[r][c] - '0') grid[r][c] = 'O';
        }
    }
    for(int r=1; r<=n; r++) {
        for(int c=1; c<=m; c++) printf("%c", grid[r][c]);
        puts("");
    }
    return 0;
}