欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

P1451 求细胞数量【深搜dfs】

程序员文章站 2022-03-20 23:02:35
题目链接#include #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...

题目链接

#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; 
	
}


本文地址:https://blog.csdn.net/qq_45159762/article/details/110175267

相关标签: 深搜dfs