ZeroJudge 解題筆記：k205. 蝸牛的踩地雷攻略 1 (插旗)

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


ZeroJudge 題目連結：k205. 蝸牛的踩地雷攻略 1 (插旗)

解題想法

我用二維陣列儲存地圖，並在周圍加上 _ 當作哨兵避免出界。依序掃過每個格子，如果這格不是數字，就跳過找下一格；如果是數字，計算周圍 8 格有幾個 # 或 P，並記錄這些位置，如果 # 及 P 的數量等於這格標記的數字，剛才記錄的位置都改成 P。

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
        cnt = 0
        bomb = []
        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] == '#' or grid[nr][nc] == 'P':
                cnt += 1
                bomb.append((nr, nc))
        if cnt == int(grid[r][c]):
            for nr, nc in bomb:
                grid[nr][nc] = 'P'
for row in grid[:n]:
    print("".join(row[:m]))

C++ 程式碼

使用時間約為 3 ms，記憶體約為 288 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 cnt = 0;
            vector<pair<int, int>> bomb;
            for(int i=0; i<8; i++) {
                int nr = r+dr[i], nc = c+dc[i];
                if (grid[nr][nc] == '#' || grid[nr][nc] == 'P') {
                    cnt++;
                    bomb.push_back(make_pair(nr, nc));
                }
            }
            if (cnt == grid[r][c] - '0') {
                for(auto it : bomb) {
                    grid[it.first][it.second] = 'P';
                }
            }
        }
    }
    for(int r=1; r<=n; r++) {
        for(int c=1; c<=m; c++) printf("%c", grid[r][c]);
        puts("");
    }
    return 0;
}