求细胞个数

一矩形阵列由数字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 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏java一日一条

有没有一段代码,让你觉得人类的智慧也可以璀璨无比?

Kyle McCormick 在 StackExchange 上发起了一个叫做 Tweetable Mathematical Art 的比赛,参赛者需要用三条推...

10430
来自专栏Java Web

会场安排问题

问题描述: 假设要在足够多的会场里安排一批活动,并希望使用尽可能少的会场。设计一个有效的贪心算法进行安排(这个问题实际上是著名的图着色问题。若将每一个活动作为图...

53740
来自专栏大数据挖掘DT机器学习

非主流自然语言处理:大规模语料词库自动生成

一、前言   写这篇文时,突然想到一个问题,大家的词库都是从哪来的?   之所以会这么有些意外的问,是因为从没把词库当成个事儿:平时处理微博,就用程序跑一下微博...

691120
来自专栏Android机动车

数据结构学习笔记——算法

算法是解决特定问题求解步骤的描述,在计算机中表现为指令的有限序列,并且每条指令表达一个或者多个步骤。

7010
来自专栏逍遥剑客的游戏开发

Puyo-Puyo设计文档

22150
来自专栏noteless

UML简单介绍-如何看懂UML(二)

你画了一个三角形说这是一个接口,我花了一个圆形,跟你讲这个是接口?这其中的问题不言而喻。

17520
来自专栏Crossin的编程教室

【Python 第53课】 数学运算

今天从打飞机游戏里中断一下,说些python的基础。 在用计算机编程解决问题的过程中,数学运算是很常用的。python自带了一些基本的数学运算方法,这节课给大家...

37140
来自专栏大数据

算法:大O符号解释

O(n),O(1),O(log n)等大O符号被用来表示算法的效率。在这篇文章中,你会找到每个大O符号的例子和解释。

28710
来自专栏大数据

大数据图:循环点阵

本文的内容最初由Marko Rodriguez和Bobby Norton在Aurelius博客上共同撰写。

35250
来自专栏一心无二用,本人只专注于基础图像算法的实现与优化。

O(1)效率的表面模糊算法优化。

     很久没有写文章了,主要是最近一段时间没有以前那么多空暇空间,内存和CPU占用率一致都很高,应前几日群里网友的要求,今天发个表面模糊的小程序来找回之前...

25560

扫码关注云+社区

领取腾讯云代金券