洪水填充是一种很简单的技巧,设置路径信息进行剪枝和统计,类似感染的过程
路径信息不撤销,来保证每一片的感染过程可以得到区分
看似是暴力递归过程,其实时间复杂度非常好,遍历次数和样本数量的规模一致
如果一个n*m的矩阵,使用洪水填充的时间复杂度O(n*m)
图中一个点最多被访问4次
purple_book 例6-12 Oil Deposits
purple_book 例6-13 Ancient Message
洪水填充
DFS的递归层数有点多
用stack 模拟栈可以防止爆栈
实质上是判断图形内部有几个白色的“洞”。
思路找相连边的同时,如果遇到0,则从0这点开始搜索并标记,统计碰到0的次数。
注意第一次碰到字母时会多算外围的0,要减去1。
要在图形外边加一圈0以避免1把0包围在边缘多算”洞”的数量