一个算法问题，大家来看看咯！

2016-05-29 12:37:10 +08:00
 coolair
0000000
0111000
1001000
0111000
1001000
1001000
1111100
如何计算被 1 包裹的 0 的个数？边缘不算
1523 次点击
所在节点    问与答
7 条回复
messyidea
2016-05-29 12:51:55 +08:00
对在边缘的每个 0 进行 dfs 啊。能访问到的 0 都标记。访问不到的那些就是被 1 包裹的
fcicq
2016-05-29 13:44:20 +08:00
典型 flood fill 问题
binux
2016-05-29 15:16:23 +08:00
扫一边不就出来了？ O(n)了你还要怎样
zhunimagebice
2016-05-29 16:47:33 +08:00
1 楼正解
hxndg
2016-05-29 19:44:57 +08:00
@messyidea 没听懂。。。能再解释么？
messyidea
2016-05-29 20:54:06 +08:00
@hxndg 你可以先去了解一下深度优先搜索，对边缘每个 0 进行深度优先搜索，这样搜到的点就一定没有被 1 包含，因为能通过很多 0 走到边界上。
jedihy
2016-05-30 03:55:58 +08:00
Number of islands leetcode 原题 dfs 或者 bfs ，本质就是穷举

这是一个专为移动设备优化的页面（即为了让你能够在 Google 搜索结果里秒开这个页面），如果你希望参与 V2EX 社区的讨论，你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/282001

V2EX 是创意工作者们的社区，是一个分享自己正在做的有趣事物、交流想法，可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX