coolair
V2EX  ›  问与答

一个算法问题,大家来看看咯!

  •  
  •   coolair · May 29, 2016 · 2246 views
    This topic created in 3809 days ago, the information mentioned may be changed or developed.
    0000000
    0111000
    1001000
    0111000
    1001000
    1001000
    1111100
    如何计算被 1 包裹的 0 的个数?边缘不算
    7 replies  •  2016-05-30 03:55:58 +08:00
    messyidea
    messyidea
    May 29, 2016 via Android
    1
    对在边缘的每个 0 进行 dfs 啊。能访问到的 0 都标记。访问不到的那些就是被 1 包裹的
    fcicq
    fcicq
    May 29, 2016
    2
    典型 flood fill 问题
    binux
    binux
    May 29, 2016 via Android
    3
    扫一边不就出来了? O(n)了你还要怎样
    zhunimagebice
    zhunimagebice
    May 29, 2016 via Android
    4
    1 楼正解
    hxndg
    hxndg
    May 29, 2016
    5
    @messyidea 没听懂。。。能再解释么?
    messyidea
    messyidea
    May 29, 2016❤️1
    6
    @hxndg 你可以先去了解一下深度优先搜索,对边缘每个 0 进行深度优先搜索,这样搜到的点就一定没有被 1 包含,因为能通过很多 0 走到边界上。
    jedihy
    jedihy
    May 30, 2016 via iPhone❤️1
    7
    Number of islands leetcode 原题 dfs 或者 bfs ,本质就是穷举
    About   ·   Help   ·   Advertise   ·   Blog   ·   API   ·   FAQ   ·   Privacy   ·   Solana   ·   1310 Online   Highest 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 46ms · UTC 22:24 · PVG 06:24 · LAX 14:24 · JFK 17:24
    ♥ Do have faith in what you're doing.