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

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

已注册用户请登录

这是一个创建于 2912 天前的主题，其中的信息可能已经有所发展或是发生改变。

0000000
0111000
1001000
0111000
1001000
1001000
1111100
如何计算被 1 包裹的 0 的个数？边缘不算

7 条回复 • 2016-05-30 03:55:58 +08:00

messyidea

2016-05-29 12:51:55 +08:00 via Android

对在边缘的每个 0 进行 dfs 啊。能访问到的 0 都标记。访问不到的那些就是被 1 包裹的

fcicq

2016-05-29 13:44:20 +08:00

典型 flood fill 问题

binux

2016-05-29 15:16:23 +08:00 via Android

扫一边不就出来了？ O(n)了你还要怎样

zhunimagebice

2016-05-29 16:47:33 +08:00 via Android

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 via iPhone

Number of islands leetcode 原题 dfs 或者 bfs ，本质就是穷举