求细胞数量

题目描述
一矩形阵列由数字0到9组成,数字1到9代表细胞,细胞的定义为沿细胞数字上下左右若还是细胞数字则为同一细胞,求给定矩形阵列的细胞个数。（1<=m,n<=100）

输入格式
输入：整数m,n(m行，n列)
矩阵

输出格式
输出：细胞的个数

输入输出样例
输入 #1
4 10
0234500067
1034560500
2045600671
0000000089
输出 #1
4

分析
这题十分简单，是一道模板搜索，DFS和BFS都可以，我用的是BFS
首先，由题意得，找出一个点，它的上下左右必须是细胞，才能加一
然后，我们再思考，四个方向的坐标和初始值
接着，我们再想判断，判断是否出现过，是否越界
最后，整个图遍历一遍，输出结果

AC代码

#include<iostream>
using namespace std;
int dx[5]={
   0,1,-1,0,0};
int dy[5]={
   0,0,0,1,-1};
int tail,head,num,st[10005][3],f[105][105],n,m,b[105][105];
char a;
void bfs(int i,int j)
{
   
	head=0;//每次都必须清零
	tail=1;//尾巴初始值
	num++;
	st[1][1]=i;//坐标
	st[1][2]=j;//坐标
	f[i][j]=1;//已经出现过
	do
	{
   
		head++;
		for(int i=1;i<=4;i++)//四个方向
		{
   
		int x=st[head][1]+dx[i],y=st[head][2]+dy[i];	
		if(x>=1&&x<=m&&y>=1&&y<=n&&f[x][y]==0&&b[x][y]!=0)//判断
		{
   
			tail++;//尾巴加1
			st[tail][1]=x;st[tail][2]=y;//更新坐标
			f[x][y]=1;//出现过
		}
	}
	}while(head<=tail);
}
int main()
{
   
	cin>>m>>n;
	for(int i=1;i<=m;i++)
	 for(int j=1;j<=n;j++)
	  {
   
	  	cin>>a;
	  	b[i][j]=a-48;
	  }
	for(int i=1;i<=m;i++)//一个一个遍历
	 for(int j=1;j<=n;j++)
	  if(b[i][j]!=0&&f[i][j]==0)bfs(i,j);	
	cout<<num;  
}

谢谢观看