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 嗯呢