全球变暖

蓝桥杯 蓝桥杯第九届 C++ DFS 所有文稿

两次dfs

/*16'34-17:02*/
#include <iostream>
#include <cmath>
#include <string.h>
using namespace std;
const int maxn=1010;
char island[maxn][maxn];
bool ma[maxn][maxn],m2[maxn][maxn]={false};
int n;
void dfs(int y,int x){
    for(int c=-1;c<=1;c++){
        for(int r=-1;r<=1;r++){
            if (r*c==0&&y+r>=0&&y+r<n&&x+c>=0&&x+c<n){
                if (island[y+r][x+c]=='#'&&!ma[y+r][x+c]){
                    ma[y+r][x+c]=true;
                    dfs(y+r,x+c);
                }
            }
        }
    }
    return;
}
int main(){
    cin>>n;
    memset(ma,false,sizeof(ma));
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>island[i][j];
        }
    }
    int cnt=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if (island[i][j]=='#'&&!ma[i][j]){
                cnt++;
                ma[i][j]=true;
                dfs(i,j);
            }
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if (!ma[i][j]){
                    for(int c=-1;c<=1;c++){
                        for(int r=-1;r<=1;r++){
                            if (r*c==0&&i+r>=0&&i+r<n&&j+c>=0&&j+c<n){
                                island[i+r][j+c]='.';
                            }
                        }
                    }
                }
            }   
        }
    cnt=0;
    memset(ma,false,sizeof(ma));
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if (island[i][j]=='#'&&!ma[i][j]){
                cnt++;
                ma[i][j]=true;
                dfs(i,j);
            }
        }
    }
    cout<<cnt;
    return 0;   
}

2019.3.3