[noip2015-普及] 扫雷游戏

题目描述

$n$ 行 $m$ 列雷区中，* 表示地雷格，? 表示非地雷格。对每个非地雷格输出其周围 8 个方向上的地雷格数量，地雷格仍输出 *。 $1 \le n, m \le 100$ 。

思路

对每个非地雷格枚举 8 个方向，先判越界再判是否地雷，累加即得该格数字。时间复杂度 $O(nm)$ 。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 11:08
# update_at: 2026-10-04 11:20

import sys

# 八个邻接方向（不含自身）：三行三屏去掉 dr=0 且 dc=0 的中心格
NEIGHBOR = [(dr, dc) for dr in (-1, 0, 1) for dc in (-1, 0, 1) if dr or dc]  # 8 个方向


def neighbor_mine_count(grid: list[str], r: int, c: int) -> int:
    """格子 (r, c) 八邻域内的地雷数：只统计仍落在雷区里的格子。"""
    n, m = len(grid), len(grid[0])
    return sum(
        grid[r + dr][c + dc] == '*'  # bool 参与求和即 0/1
        for dr, dc in NEIGHBOR
        if 0 <= r + dr < n and 0 <= c + dc < m  # 越界方向直接丢弃，防止负下标回绕
    )


def render(grid: list[str]) -> list[str]:
    """生成输出雷区：地雷格保持 '*'，非地雷格换成八邻域地雷数。"""
    return [
        ''.join(cell if cell == '*' else str(neighbor_mine_count(grid, r, c))
                for c, cell in enumerate(row))
        for r, row in enumerate(grid)
    ]


def solve() -> None:
    # 行本身是完整 token（行内无空格），split() 后按输入顺序 next() 消费即可
    data = iter(sys.stdin.buffer.read().split())
    n, m = int(next(data)), int(next(data))  # 两个位置量先命名
    grid = [next(data).decode() for _ in range(n)]  # 每行 m 个字符，相邻无分隔符
    print('\n'.join(render(grid)))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 15:25
 * update_at: 2026-10-06 15:25
 */

#include <iostream>
#include <cstdio>
using namespace std;

typedef long long ll;

const int MAXN = 105; // 题目 n, m <= 100

int n, m;
char grid[MAXN][MAXN];

// 8 个方向偏移：三行三列去掉中心 (0,0)
int dr[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dc[8] = {-1, 0, 1, -1, 1, -1, 0, 1};

// 计算 (r, c) 八邻域内且仍在雷区中的地雷数
int count_neighbor_mines(int r, int c) {
    int cnt = 0;
    for (int i = 0; i < 8; i++) {
        int nr = r + dr[i];
        int nc = c + dc[i];
        if (nr >= 1 && nr <= n && nc >= 1 && nc <= m) { // 越界方向直接丢弃
            if (grid[nr][nc] == '*') cnt++;
        }
    }
    return cnt;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> (grid[i] + 1); // 从 grid[i][1] 开始读入 m 个字符
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (grid[i][j] == '*') {
                cout << '*';
            } else {
                cout << count_neighbor_mines(i, j);
            }
        }
        cout << '\n';
    }

    return 0;
}

[noip2015-普及] 扫雷游戏

目录

题目描述

思路

参考代码