解题思路

扫雷游戏我们小时候都玩过：点开一个不是地雷的格子，它就会告诉我们周围一圈藏着几颗雷。所谓"周围一圈"，包括上、下、左、右、左上、右上、左下、右下，一共8个格子。

现在任务反过来：题目把地雷的分布告诉我们了（*表示地雷，?表示空地），要我们算出每个空地上应该显示的数字。

这道题的做法非常"笨"却非常有效：

1. 先把整个雷区读进来，存在一个二维字符数组里。比如 a[i][j] 就表示第 i 行第 j 列的格子。
2. 然后一格一格地检查：
   • 如果这一格本身就是地雷 *，就直接输出 *（题目要求地雷仍然显示 *）；
   • 如果这一格是空地 ?，就去数一数它周围8个格子里有几个地雷 *，把这个数字输出来。
3. 数周围8个格子的时候，可以用一个小技巧：准备两个数组 dx 和 dy，分别记录8个方向的"行变化"和"列变化"。比如"左上"就是行减1、列减1。这样用一个 for 循环就能把所有方向都看一遍，代码又短又不容易漏方向。

这里有一个特别容易犯错的地方——越界。比如最左上角那一格（第0行第0列），它的左边、上边都不存在。如果我们硬去访问数组外面的格子，程序就会出错（可能读到脏数据）。所以每次检查一个邻居之前，要先判断它的行号、列号是否真的在雷区范围内（第0行到第n-1行、第0列到第m-1列）。

输出的时候注意：一行一行输出，每行结束后要换行。

参考代码

// 扫雷游戏：计算每个非地雷格周围（8个方向）的地雷个数
#include <iostream>
#include <string>
using namespace std;
int main(){
    int n,m;
    cin>>n>>m;
    string a[105];                    // 用字符串数组存雷区
    for(int i=0;i<n;i++) cin>>a[i];   // 读入n行雷区
    // 八个方向的偏移：上、下、左、右、左上、右上、左下、右下
    int dx[8]={-1,1,0,0,-1,-1,1,1};
    int dy[8]={0,0,-1,1,-1,1,-1,1};
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(a[i][j]=='*'){ cout<<'*'; continue; } // 地雷格原样输出
            int cnt=0; // cnt记录周围地雷个数
            for(int k=0;k<8;k++){
                int x=i+dx[k], y=j+dy[k];
                // 判断相邻格是否在雷区范围内且是地雷
                if(x>=0&&x<n&&y>=0&&y<m&&a[x][y]=='*') cnt++;
            }
            cout<<cnt; // 输出周围地雷数
        }
        cout<<'\n';
    }
    return 0;
}

复杂度分析

雷区一共 n 行 m 列，也就是 n×m 个格子。每一个格子我们最多去看8个邻居，所以总的工作量大约是 8×n×m 次。用大O记号写就是：

• 时间复杂度：O(n×m)。n 和 m 最大都是100，最多算 100×100=10000 个格子，非常快。
• 空间复杂度：O(n×m)，因为我们用了一个和雷区一样大的二维数组来存地图。