题解案例都过了,但是12分,蒟蒻求调(不长)
查看原帖
题解案例都过了,但是12分,蒟蒻求调(不长)
830594
HLQ12楼主2024/3/1 00:27
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define first h
#define second l


char a[1004][1004];//初始地图
char aft[1004][1004];//淹没后地图
int ans = 0;
void dfs(int x, int y){
    if(a[x][y] == '.' || a[x][y] == 'x'){
        return;
    }
    aft[x][y] = '.';
    a[x][y] = '.';
    dfs(x+1, y);
    dfs(x-1, y);
    dfs(x, y+1);
    dfs(x, y-1);

}


int main(){
    for(int i = 0; i <= 1001; i++){
        a[i][0] = 'x';
        a[0][i] = 'x';
        a[1001][i] = 'x';
        a[i][1001] = 'x';
    }


    int n;
    cin>>n;

    for(int i = 1; i <=n; i++){
         for(int j = 1; j<=n; j++){
            cin>>a[i][j];
        }
    }

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            if(a[i][j] == '#'){
                if(a[i-1][j] == '.' || a[i+1][j] == '.' || a[i][j-1] == '.' || a[i][j+1] == '.'){
                    aft[i][j] = '.';
                }else{
                    aft[i][j] = '#';
                }
            }else{
                aft[i][j] = '.';
            }
        }
    }

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            if(aft[i][j] == '#'){
              //淹没后还有陆地存在,就在被淹没前的大陆dfs,把原来大陆的坐标都修改为海洋,淹没后的也修改为海洋,避免寻找同一个大陆分裂出来的岛屿
                dfs(i, j);
                ans++;
            }
        }
    }

    cout<<ans<<endl;
    return 0;
}
2024/3/1 00:27
加载中...