12分求调

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

ragwort @ 2023-01-14 18:43:30

#include <bits/stdc++.h>
using namespace std;
const int N = 1005;

int n,a[N][N],k;
char wind_kaka;
bool chen_zhe;

void dfs(int x,int y){
    a[x][y] = -1;
    if(!(a[x-1][y] == 0 || a[x+1][y] == 0 || a[x][y-1] == 0 || a[x][y+1] == 0)){
        if(chen_zhe) k++;
        chen_zhe = false;
    }
    if(a[x-1][y] == 1) dfs(x-1,y);
    if(a[x+1][y] == 1) dfs(x+1,y);
    if(a[x][y+1] == 1) dfs(x,y+1);
    if(a[x][y-1] == 1) dfs(x,y-1);
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(NULL);

    //memset(a,-1,sizeof(a));

    cin >> n;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            cin >> wind_kaka;
            if(wind_kaka == '#')
                a[i][j] = 1;
            else a[i][j] = 0;
        }
    }

    /*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] == 1){
                chen_zhe = true;
                dfs(i,j);
            }
        }
    }

    cout << k << endl;

    /*for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            cout << a[i][j];
        }
        cout << endl;
    }*/
    return 0;
}

谢谢


by ragwort @ 2023-01-14 18:43:54

代码挺干净的


by Loser_Syx @ 2023-01-14 18:46:06

所以为啥有个变量名叫chen_zhe


by ragwort @ 2023-01-14 18:48:27

@Saint_ying_xtf (


by William_Takazaki @ 2023-01-14 18:49:42

@wind_kaka

https://www.luogu.com.cn/discuss/557967

https://www.luogu.com.cn/discuss/558003


by ragwort @ 2023-01-14 18:50:44

@6371 %


by ragwort @ 2023-01-14 18:55:11

@6371 哦我计算的是完全淹没的,只要计算for循环里调用了几次dfs,在减去k就行了

for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            if(a[i][j] == 1){
                cnt++;
                chen_zhe = true;
                dfs(i,j);
            }
        }
    }

    cout << cnt-k << endl;

by Infinty @ 2023-01-14 19:03:25

@wind_kaka 原神算法可以解决这个题


by Infinty @ 2023-01-14 19:03:45

你可以用超级元神算法解决。


by ragwort @ 2023-01-14 22:27:08

@Dont_view_my_profile 嗯呢


|