洛谷 P4961-蒲公英云

洛谷 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; }