当前位置:首页 > 搜索 > 正文
SSOJ2316面积
6442+

题目大意:对于给定的10*10的01矩阵,请问有多少个0被1包围了?(包围是指不能由上下左右通向边缘)

题目描述

编程计算由“1”号围成的下列图形的面积。面积计算方法是统计1号所围成的闭合曲线中点的数目。如图所示,在10*10的二维数组中,“1”围住了15个点,因此面积为15.

0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 1 1 0 0 0
0 0 0 0 1 0 0 1 0 0
0 0 0 0 0 1 0 0 1 0
0 0 1 0 0 0 1 0 1 0
0 1 0 1 0 1 0 0 1 0
0 1 0 0 1 1 0 1 1 0
0 0 1 0 0 0 0 1 0 0
0 0 0 1 1 1 1 1 0 0
0 0 0 0 0 0 0 0 0 0

输入

一个由0和1组成的10*10的二维数组

输出

符号“1”围住的“0”的个数,即围成的面积

样例输入

0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 1 1 0 0 0
0 0 0 0 1 0 0 1 0 0
0 0 0 0 0 1 0 0 1 0
0 0 1 0 0 0 1 0 1 0
0 1 0 1 0 1 0 0 1 0
0 1 0 0 1 1 0 1 1 0
0 0 1 0 0 0 0 1 0 0
0 0 0 1 1 1 1 1 0 0
0 0 0 0 0 0 0 0 0 0

样例输出

15

解题思路

图形学中Flood Fill是满水法填充,是用来填充区域的。就好比在一个地方一直到水,水会往四周满延开,直到高地阻挡。Flood Fill就是从一个点开始往四周寻找相同的点填充,直到有不同的点为止。 Flood Fill既可以用深度优先搜索实现,也可以用广度优先搜索实现,由于每个点只会被访问一次,两种算法的时间复杂度差不多。

本题中,要求被1包围的0有多少个,那么我们可以把没被1包围的0全部都填充成1,最后再数一下有多少个1即可。

什么是没被1包围的0?边缘的0都是没被包围的,只有与边缘的0相连就不被包围。因此,我们可以搜索每个边缘的0,并将他以及与他相连的0全部变为1。

小技巧:在读入数据之前,让mp数组各个元素都是非0,这样即使搜索到了mp[0][i]或者mp[i][0],也不会走出地图,因为遇到0才继续走。

程序实现

SSOJ2316面积:等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!