求细胞个数
一矩形阵列由数字0到9组成,数字1到9代表细胞,细胞的定义为沿细胞数字上下左右还是细胞数字则为同一细胞,求给定矩形阵列的细胞个数。如:
阵列 4 10
0234500067
1034560500
2045600671
0000000089
有4个细胞。
【算法分析】
⑴从文件中读入m*n矩阵阵列，将其转换为bool矩阵存入b数组中； ⑵沿b数组矩阵从上到下，从左到右，找到遇到的第一个细胞； ⑶将细胞的位置入队h，并沿其上、下、左、右四个方向上的细胞位置入队，入队后的位置b数组置为flase；
⑷将h队的队头出队，沿其上、下、左、右四个方向上的细胞位置入队，入队后的位置b数组置为flase； ⑸重复4，直至h队空为止，则此时找出了一个细胞； ⑹重复2，直至矩阵找不到细胞； ⑺输出找到的细胞数。
1 #include<iostream>
2 #include<cstdio>
3 using namespace std;
4 int a[101][101];
5 int xx[5]={-1,1,0,0};
6 int yy[5]={0,0,-1,+1};
7 int tot=0;
8 int n,m;
9 void dfs(int i,int j)
10 {
11 for(int k=0;k<4;k++)
12 {
13 if(i+xx[k]>=1&&j+yy[k]>=1&&i+xx[k]<=n&&j+yy[k]<=m&&a[i+xx[k]][j+yy[k]]==1)
14 {
15 a[i+xx[k]][j+yy[k]]=0;
16 dfs(i+xx[k],j+yy[k]);
17 }
18 }
19 }
20 int main()
21 {
22 char p[101];
23 cin>>n>>m;
24 for(int i=1;i<=n;i++)
25 {
26 scanf("%s",p);
27 for(int j=1;j<=m;j++)
28 {
29 int d=p[j-1]-48;
30 if(d==0)
31 a[i][j]=0;
32 else
33 a[i][j]=1;
34 }
35 }
36 /*for(int i=1;i<=n;i++)
37 {
38 for(int j=1;j<=m;j++)
39 {
40 int d;
41 cin>>d;
42 if(d!=0)
43 a[i][j]=1;
44 else
45 a[i][j]=0;
46 }
47 }*/
48 for(int i=1;i<=n;i++)
49 {
50 for(int j=1;j<=m;j++)
51 {
52 if(a[i][j]==1)
53 {
54 a[i][j]=0;
55 dfs(i,j);
56 tot++;
57 }
58 }
59 }
60 cout<<tot;
61 return 0;
62 }本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017-03-28 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读