当前位置:首页 > 搜索 > 正文
SSOJ2314细胞
934+

题目大意:一矩形阵列由数字0到9组成,正数代表细胞,上下左右相连的正数是同一个细胞,共有多少个细胞?。

题目描述

一矩形阵列由数字0到9组成,数字1到9代表细胞,细胞的定义为沿细胞数字上下左右还是细胞数字则为同一细胞,求给定矩形阵列的细胞个数。

如:

4 10

0234500067

1034560500

2045600671

0000000089

有4个细胞。

输入

第1行,输入m,n;m,n分别表示矩阵有m行和n列。

接下来的m行,每行输入n个数字

输出

输出矩形阵列中的细胞数

样例输入

4 10
0234500067
1034560500
2045600671
0000000089

样例输出

4

提示

n、m不超过100

解题思路

Flood Fill算法:遍历整个阵列,遇到正数就往四个方向搜索,如果搜索到的点是正数,则继续往四个方向搜索,将所有搜索过的点标记为0,即下次不会再搜索到他。这样,遍历遇到多少个正数,就有多少个细胞。由于不会重复搜索,深搜和广搜时间复杂度相同,即O(m*n)。

程序实现

更多
SSOJ2314细胞:等您坐沙发呢!

发表评论

😉😐😡😈🙂😯🙁🙄😛😳😮mrgreen.png😆💡😀👿😥😎😕

快捷键:Ctrl+Enter