2019-09-05 19:17:42 C++

C++

Copy Copied! Full
#include <bits/stdc++.h> using namespace std; #define P pair<int,int> int s[1005][1005]; int H,W,ans = 0; int dx[8] = {-1,-1,-1,0,0,1,1,1}; int dy[8] = {-1,0,1,-1,1,-1,0,1}; bool check(int score,int x,int y){ int t = 0; for(int i=0;i<8;i++){ if(x+dx[i]<1||x+dx[i]>H||y+dy[i]<1||y+dy[i]>W)continue; if(s[x+dx[i]][y+dy[i]]==-1)t++; } if(t>=score)return true; else return false; } int main(void){ bool ok = 0; queue<P> q,q2; cin >> H >> W; for(int i=1;i<=H;i++)for(int j=1;j<=W;j++){ char c;cin >> c; if(c=='.')s[i][j]=-1; else s[i][j] = c-'0'; } for(int i=1;i<=H;i++)for(int j=1;j<=W;j++){ if(s[i][j]>0){ if(check(s[i][j],i,j)){ q.push(P(i,j)); ok = 1; } } } if(ok)ans++; while(ok){ ok = 0; while(!q.empty()){ P p = q.front();q.pop(); q2.push(p); s[p.first][p.second]=-1; } while(!q2.empty()){ P p = q2.front();q2.pop(); for(int i=0;i<8;i++){ int nx = p.first + dx[i]; int ny = p.second+ dy[i]; if(nx<1||ny<1||nx>H||ny>W)continue; if(check(s[nx][ny],nx,ny)){ q.push(P(nx,ny)); ok = 1; } } } if(ok)ans++; } cout << ans << endl; }