P1451 求细胞数量【深搜dfs】

作者: 秃头短腿大肚皮的郑某人
来源: 51数据库
2021-08-31

题目链接

#include<bits/stdc++.h> 
#define go(i,n,m) for(int i=n;i<=m;i++)
#define ro(i,n,m) for(int i=n;i>=m;i--)
using namespace std;
int a[105][105];
int dx[]={0,0,0,-1,1};
int dy[]={0,1,-1,0,0};//第一个表示不动，是充数的，后面的四个分别是上下左右四个方向
int n,m,ans;

void dfs(int x,int y)
{
	if(x<0||y<0||x>n||y>m)//如果搜过头或者已经被搜过了或者本来就是墙的就往回
		return;
	else
	{
		a[x][y]=0;//染色 
		go(i,1,4){
			if(a[x+dx[i]][y+dy[i]])
				dfs(x+dx[i],y+dy[i]);//如果有才广搜 
		}
	}
}

int main(){
	cin>>n>>m;
	go(i,0,n-1){
		go(j,0,m-1){
			scanf("%1d",&a[i][j]);
		}
	}
	go(i,0,n-1){
		go(j,0,m-1){
			if(a[i][j])ans++,dfs(i,j);//如果是细胞就深搜看看 
		}
	}
	cout<<ans; 
	
}