1329：【例8.2】细胞
时间限制: 1000 ms 内存限制: 65536 KB
提交数: 29369 通过数: 16593
【题目描述】
一矩形阵列由数字00到99组成,数字11到99代表细胞,细胞的定义为沿细胞数字上下左右还是细胞数字则为同一细胞,求给定矩形阵列的细胞个数。如:
阵列
4 10 0 0000000089
有44个细胞。
【输入】
第一行为矩阵的行nn和列mm;
下面为一个n×mn×m的矩阵。
【输出】
细胞个数。
【输入样例】
4 10 0 0000000089
【输出样例】
4
代码：
bfs：
#include <bits/stdc++.h> using namespace std; int sum,n,m; char a[105][105]; int f[105][105]; int dx[4]= {0,-1,0,1}; //左 上 右 下 int dy[4]= {-1,0,1,0}; struct zb { int x,y; }; queue <zb> q; void bfs(int i,int j) { zb t= {i,j}; q.push(t); while(!q.empty()) { zb top=q.front(); q.pop(); for(int i=0; i<4; i++) { int tx=top.x+dx[i]; int ty=top.y+dy[i]; if(tx>=1&&tx<=n&&ty>=1&&ty<=m) { if(a[tx][ty]!='0'&&f[tx][ty]==0) { f[tx][ty]=1; t= {tx,ty}; q.push(t); } } } } } int main() { cin>>n>>m; for(int i=1; i<=n; i++) { for(int j=1; j<=m; j++) { cin>>a[i][j]; } } for(int i=1; i<=n; i++) { for(int j=1; j<=m; j++) { if(a[i][j]!='0'&&f[i][j]==0) { sum++; f[i][j]=1; bfs(i,j); } } } cout<<sum<<endl; return 0; }dfs:
#include <bits/stdc++.h> using namespace std; int dx[4]= {-1,1,0,0}; int dy[4]= {0,0,-1,1}; char a[105][105]; int f[105][105]; int n,m,cnt; void dfs(int x,int y) { for(int i=0; i<4; i++) { int tx=x+dx[i]; int ty=y+dy[i]; if(tx>=1&&tx<=n&&ty>=1&&ty<=m) { if(a[tx][ty]!='0'&&f[tx][ty]==0) { f[tx][ty]=1; dfs(tx,ty); } } } } int main () { cin>>n>>m; for(int i=1; i<=n; i++) { for(int j=1; j<=m; j++) { cin>>a[i][j]; } } for(int i=1; i<=n; i++) { for(int j=1; j<=m; j++) { if(a[i][j]!='0'&&f[i][j]==0) { cnt++; f[i][j]=1; dfs(i,j); } } } cout<<cnt; return 0; }
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
如需转载请保留出处：https://bianchenghao.cn/bian-cheng-ji-chu/78532.html