题解 | 分割后处理

#include <iostream>
#include <vector>
using namespace std;
int m,n;
vector<vector<int>>res={{0,1},{0,-1},{1,0},{-1,0}};
void fill_water(vector<vector<int>>&memo,int i,int j){
      for(int k=0;k<4;++k){
        int x=i+res[k][0],y=j+res[k][1];
        if(x>=0&&x<m&&y>=0&&y<n&&memo[x][y]==0){
            memo[x][y]=2;
            fill_water(memo, x, y);
        }
      }
   }
   void fill_land(vector<vector<int>>&memo,int i,int j){
    for(int k=0;k<4;++k){
        int x=i+res[k][0],y=j+res[k][1];
        if(x>=0&&x<m&&y>=0&&y<n&&(memo[x][y]==0||memo[x][y]==1)){
            memo[x][y]=3;
            fill_land(memo, x,y);
        }
    }
   }
int main() {
    cin>>m>>n;
    vector<vector<int>>memo(m,vector<int>(n));
    for(int i=0;i<m;++i){
        for(int j=0;j<n;++j){
            cin>>memo[i][j];
        }
    }
    // 先填满水域
    for(int j=0;j<n;++j){
        if(memo[0][j]==0){
        memo[0][j]=2;
        fill_water(memo,0,j);
        }
    }
    for(int i=1;i<m;++i){
        if(memo[i][0]==0){
            memo[i][0]=2;
            fill_water(memo,i,0);
        }
        if(memo[i][n-1]==0){
            memo[i][n-1]=2;
            fill_water(memo,i,n-1);
        }
    }
    // 再填满有效陆域
    for(int j=0;j<n;++j){
        if(memo[m-1][j]==1){
            memo[m-1][j]=3;
            fill_land(memo,m-1,j);
        }
    }
    int sum=0;
    for(int i=0;i<m;++i){
        for(int j=0;j<n;++j){
            if(memo[i][j]==3){
                sum+=1;
            }
        }
        
    }
    cout<<sum<<endl;
}
// 64 位输出请用 printf("%lld")