P2670 [NOIP 2015 普及组] 扫雷游戏——题解

解题思路

枚举每个格子。若是地雷直接输出；否则枚举八个方向，判断相邻坐标是否在棋盘内且为地雷，累加后输出。

复杂度分析

时间复杂度 $O(nm)$，空间复杂度 $O(nm)$。

C++17 参考代码

#include <bits/stdc++.h>
using namespace std;
char a[105][105];
int main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);
    int n,m;cin>>n>>m;
    for(int i=0;i<n;i++) cin>>a[i];
    int dx[8]={-1,-1,-1,0,0,1,1,1};
    int dy[8]={-1,0,1,-1,1,-1,0,1};
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(a[i][j]=='*'){cout<<'*';continue;}
            int cnt=0;
            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;
}

#include <bits/stdc++.h> using namespace std; char a[105][105]; int main(){ ios::sync_with_stdio(false);cin.tie(nullptr); int n,m;cin>>n>>m; for(int i=0;i<n;i++) cin>>a[i]; int dx[8]={-1,-1,-1,0,0,1,1,1}; int dy[8]={-1,0,1,-1,1,-1,0,1}; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ if(a[i][j]''){cout<<'';continue;} int cnt=0; 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; }