题目描述
一矩形阵列由数字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; else a[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