题解：P16486 [GKS 2014 #C] Minesweeper

· · 题解

题解：P16486 [GKS 2014 #C] Minesweeper

解题思路

依旧数据很少，可以用深搜，先预处理格子周围的地雷数量，再寻找不是地雷的格子开始深搜（深搜过程其实类似连通块问题），每深搜一次步数加一，最终按格式（空格加了吗）输出即可。

注意

多测需清空。

正确代码

#include<bits/stdc++.h>
using namespace std;
int n;
char mp[305][305];//地图 
int dl[305][305];// 格子周围的地雷数量 
bool vis[305][305];//判断是否走过
int dx[8]={1, 1, 0, -1, -1, -1, 0, 1};
int dy[8]={0, 1, 1, 1, 0, -1, -1, -1};
bool ok(int x,int y){
    return x>=0&&x<n&&y>=0&&y<n;
}//判断是否在网格内  
void dlsl(){
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(mp[i][j]=='*'){
                dl[i][j]=-1;//标记地雷 
                continue;
            }
            int cnt=0;
            for(int k=0;k<8;k++){
                int nx=i+dx[k];
                int ny=j+dy[k];
                if(ok(nx,ny)&&mp[nx][ny]=='*'){
                    cnt++;
                }
            }
            dl[i][j]=cnt;
        }
    }
} 
void dfs(int x,int y){
    vis[x][y]=true;
    if(dl[x][y]>0)return;
    for(int k=0;k<8;k++){
        int nx=x+dx[k];
        int ny=y+dy[k];
        if(ok(nx,ny)&&!vis[nx][ny]&&mp[nx][ny]!='*'){
            vis[nx][ny]=true;
            if(!dl[nx][ny]){
                dfs(nx,ny);
            }
        }
    }

}
int main() {
    int t;
    cin>>t;
    for(int tt=1;tt<=t;tt++){
        cin>>n;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                cin>>mp[i][j];
            }
        }
        memset(vis,0,sizeof(vis));//多测需清空 
        dlsl();
        int step=0;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(mp[i][j]!='*'&&!vis[i][j]&&dl[i][j]==0){
                    step++;
                    dfs(i,j);
                }
            }
        } 
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(mp[i][j]!='*'&&!vis[i][j]){
                    step++;
                    vis[i][j]=true;
                }
            }
        } 
        cout<<"Case #"<<tt<<": "<<step<<endl;//空格没打硬控15分钟
    }
    return 0; 
}