G4025 [GESP202606 四级] 扫雷 题解

知识点：二维数组、邻域计数、模拟。

解题思路

读入每个雷的位置，标记该格，并给它周围3×3范围内的计数加1。输出时雷格为*，其他格为累计雷数。

为什么正确

每颗雷恰给所有邻格贡献1，叠加后每个非雷格的数值就是相邻雷总数。

易错点

计数覆盖中心无妨，因为雷格最终输出*；坐标减1后要夹紧边界。

复杂度

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

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m,q;
    cin>>n>>m>>q;
    vector<vector<int>>a(n,vector<int>(m)),cnt(n,vector<int>(m));
    while(q--) {
        int i,j;
        cin>>i>>j;
        --i;
        --j;
        a[i][j]=1;
        for(int x=max(0,i-1);x<=min(n-1,i+1);x++)for(int y=max(0,j-1);y<=min(m-1,j+1);y++)cnt[x][y]++;
    }
    for(int i=0;i<n;i++) {
        for(int j=0;j<m;j++) {
            if(a[i][j])cout<<"*";
            else cout<<cnt[i][j];
            cout<<(j==m-1?"\n":" ");
        }
    }
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用8个自行生成的测试点。