洛谷 P4961

目录

• code

题目

戳
为了小埋a了这道题。

思路

读入原来的矩阵，将不是雷的格子更新为数字（数字就是该格子周围八格的雷的个数）将是雷的格子赋值为inf。然后就按照题目要求计算周围八格没有“空格”的“数字”个数和“空"的个数。

code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<iomanip>
#include<algorithm>
using namespace std;
const int inf=0x3f3f3f;
int n,m,sum1,sum2;
int dx[10]={0,1,-1,1,1,-1,-1,0,0},dy[10]={0,0,0,1,-1,1,-1,1,-1};
bool map0[1001][1001];
int map1[1001][1001];
inline int read(){
    int x=0;
    bool f=0;
    char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=!f;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return f?-x:x;
}//读优
void js(int x,int y){
    int sum=0;
    for(int i=1;i<=8;++i){
        int c=x+dx[i],d=y+dy[i];
        if(c>0&&c<=n&&d>0&&d<=m&&map0[c][d]) sum++;
    }
    map1[x][y]=sum;
}//更新数字的函数
bool pd(int x,int y){
    bool qaq=0;
    for(int i=1;i<=8;++i){
        int c=x+dx[i],d=y+dy[i];
        if(c>0&&c<=n&&d>0&&d<=m&&map1[c][d]==0){
            qaq=1;
            break;
        }
    }
    if(qaq) return false;
    return true;
}
void k(int x,int y){
    map1[x][y]=-1;
    for(int i=1;i<=8;++i){
        int c=x+dx[i],d=y+dy[i];
        if(c>0&&c<=n&&d>0&&d<=m&&map1[c][d]==0){
            k(c,d);
        }
    }
}

int main(){
    n=read();m=read();
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            map0[i][j]=read();
            if(map0[i][j]) map1[i][j]=inf;
        }
    }//读入，和预处理。
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            if(!map0[i][j]) js(i,j);
        }
    }//更新数字。
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            if(map1[i][j]!=0&&map1[i][j]!=inf){
                if(pd(i,j)) sum1++;
            }
        }
    }//计算周围八格没有空格的个数
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            if(map1[i][j]==0){
                k(i,j);
                sum2++;
            }
        }
    }//计算空的个数
    cout<<sum1+sum2;
    return 0;
}