【例62.3】 地雷数计算

解题思路

保存原始雷区。地雷原样输出；非地雷格枚举周围8个偏移，统计合法坐标中原字符为*的数量，输出该数字。

正确性说明

依题目给出的对应关系逐项处理，位置与原输入保持明确对应。每一步完成当前项的全部贡献，结束后得到所有位置或字符的目标结果。

易错点

统计不能基于已修改的输出图；边界先判坐标。

复杂度

时间O(nm)，空间O(nm)。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<string> a(n);
    for (auto &s : a)
        cin >> s;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (a[i][j] == '*') {
                cout << '*';
                continue;
            }
            int count = 0;
            for (int dx = -1; dx <= 1; dx++)
                for (int dy = -1; dy <= 1; dy++) {
                    if (dx == 0 && dy == 0)
                        continue;
                    int x = i + dx, y = j + dy;
                    if (x >= 0 && x < n && y >= 0 && y < m && a[x][y] == '*')
                        count++;
                }
            cout << count;
        }
        cout << "\n";
    }
    return 0;
}