10WAdfs求助
  • 板块灌水区
  • 楼主caramel_qwq
  • 当前回复1
  • 已保存回复1
  • 发布时间2022/6/14 20:23
  • 上次更新2023/10/27 23:18:39
查看原帖
10WAdfs求助
444195
caramel_qwq楼主2022/6/14 20:23

思路是先把所有空地设成1,统计所有1的数量,如果真的可以淹没就改成2,计数器-1,最后输出的计数器就是没被淹没的空地的数量。

#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
int n,m,cnt=0;
char a[508][508];
void dfs(int x,int y){
	a[x][y]='2';
	cnt--;
	if(x-1>=1&&a[x-1][y]=='1') dfs(x-1,y);
	if(x+1<=n&&a[x+1][y]=='1') dfs(x+1,y);
	if(y-1>=1&&a[x][y-1]=='1') dfs(x,y-1);
	if(y+1<=m&&a[x][y+1]=='1') dfs(x,y+1);
	return ;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
			if(a[i][j]=='0'){
				a[i][j]='1';
				cnt++;
			}
		} 
	}
	for(int i=1;i<=max(n,m);i++){
		if(a[1][i]=='1') dfs(1,i);
		if(a[i][1]=='1') dfs(i,1);
		if(a[n][i]=='1') dfs(n,i);
		if(a[i][n]=='1') dfs(i,n);
	}
	cout<<cnt<<"\n";
	return 0;
} 
2022/6/14 20:23
加载中...