题目描述
一矩形阵列由数字0到9组成,数字1到9代表细胞,细胞的定义为沿细胞数字上下左右若还是细胞数字则为同一细胞,求给定矩形阵列的细胞个数。（1<=m,n<=100）?
输入输出格式
输入格式：
输入：整数m,n(m行，n列)
矩阵
输出格式：
输出：细胞的个数
BFS新手入门
这是一题裸得十分善良的搜索（善良到无记忆深搜都能快乐AC）
正片：
1.题意阅读：（读入）
一矩形阵列由数字0到9组成,数字1到9代表细胞,细胞的定义为沿细胞数字上下左右若还是细胞数字则为同一细胞。
这就意味着其实这题的读入只有两种分化
①没有细胞②有细胞（熟悉的bool数据）
所以在读入时我们就可以直接进行预处理
if（有细胞）
a[i][j]=1;
else
a[i][j]=0;
2.核心算法：（BFS）
BFS的核心就是找到一个合法节点后将其往外展开，判断后压如队列 （其实我也解释不清，还是看代码意会吧。。。）
//q[..][2]这是一个数组模拟的队列 //c[..][..]是方向数组 void bfs(int i,int j){//发现a[i][j]合法后的处理int head=0,tail=1;ans++;//一个新的细胞q[head][0]=i;q[head][1]=j;//将此合法点作为队首进行记录while(head<tail){//队伍搜完了，完整细胞已完全展开i=q[head][0];j=q[head][1];//队首弹出搜索for(int k=0;k<4;++k){if(a[i+c[k][0]][j+c[k][1]]){//如果这个节点可以访问q[tail][0]=i+c[k][0];q[tail][1]=j+c[k][1];a[q[tail][0]][q[tail][1]]=0;//将已经放进队列等待搜索的数标记成不可走//这样就不会导致重复对一个节点的访问++tail;}}++head;//已搜索节点删除}//一口气搜到没有连接在一起的合法节点 }
这段代码中，蒟蒻是直接将 无细胞 与 已发现节点 归为不可走节点的，全部用a[..][..]进行保存，不过当题目搜索条件复杂时，还是推荐按照条件分类使用多个数组进行保存记录，这样比较清晰。
3.分析
仔细一想好像效率也没比DFS小多少
最后奉上丑陋代码：
#include<bits/stdc++.h> #define ll long long using namespace std; bool a[201][201]; int q[100005][2]; ll m,n,ans; int c[4][2]={0,1,-1,0,1,0,0,-1}; void bfs(int i,int j){int head=0,tail=1;ans++;q[head][0]=i;q[head][1]=j;while(head<tail){i=q[head][0];j=q[head][1];for(int k=0;k<4;++k){if(a[i+c[k][0]][j+c[k][1]]){q[tail][0]=i+c[k][0];q[tail][1]=j+c[k][1];a[q[tail][0]][q[tail][1]]=0;++tail;}}++head;} } int main(){cin>>m>>n;char b;for(int i=1;i<=m;++i){for(int j=1;j<=n;++j){cin>>b;if(b=='0')a[i][j]=0;elsea[i][j]=1;}}for(int i=1;i<=m;++i){for(int j=1;j<=n;++j){if(a[i][j]){bfs(i,j);}}}cout<<ans<<endl;}
恳请指点鸭 O(∩_∩)O