太难了!

P8662 [蓝桥杯 2018 省 AB] 全球变暖

20190209x @ 2024-11-30 17:32:20

#include<bits/stdc++.h>
using namespace std;
int n,a[1010][1010],summ;
char b[1010][1010];
int g[3][1000000],f,r,dx[5]={0,0,-1,0,1},dy[5]={0,-1,0,1,0};
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>b[i][j];
            if(b[i][j]=='#'){
                a[i][j]=1;
            }
        }
    }
    for(int i=2;i<=n-1;i++){
        for(int j=2;j<=n-1;j++){
            if(a[i][j]==1){
                for(int k=1;k<=4;k++){
                    int x=i+dx[k],y=j+dy[k];
                    if(a[x][y]==0){
                        a[i][j]=2;
                        break;
                    }
                }
            }
        }
    }
/*  for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cout<<a[i][j]<<" ";
        }
        cout<<endl;
    }*/
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(a[i][j]==2){
                bool flag=1;
                r=f=1;
                g[1][r]=i;
                g[2][r]=j;
                a[i][j]=0;
                while(r>=f){
                    for(int k=1;k<=4;k++){
                        int x=g[1][f]+dx[k],y=g[2][f]+dy[k];
                        if(a[x][y]==1){
                            flag=0;
                            a[x][y]=0;
                        }
                        if(a[x][y]==2){
                            r++;
                            g[1][r]=x;
                            g[2][r]=y;
                            a[x][y]=0;
                        }
                    }
                    f++;
                }
                if(flag){
                    ++summ;
                }
            }
        }
    }
/*  for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cout<<a[i][j]<<" ";
        }
        cout<<endl;
    }*/
    cout<<summ;
    return 0;
}

by DDD_et @ 2024-11-30 17:44:17

不就一洪水填充吗,哪里难了


|