My-Notes

Search

SearchSearch

040.洪水填充

Dec 29, 2023, 10 min read

前置知识：常见经典递归过程解析，其中的带路径的递归过程解析

洪水填充是一种很简单的技巧，递归过程中设置路径信息进行剪枝和统计，类似感染的过程

路径信息不撤销，来保证每一片的感染过程可以得到区分

看似是暴力递归过程，其实时间复杂度非常好，遍历次数和样本数量的规模一致

题目1.岛屿数量

岛屿数量-并查集做法

洪水填充做法

var (
	n int
	m int
	theGrid [][]byte
)
 
func numIslands(grid [][]byte) int {
	n = len(grid)
	if n == 0 {
		return 0
	}
	m = len(grid[0])
	theGrid = grid
	ans := 0
 
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			if grid[i][j] == '1' {
				dfs(i, j)
				ans++
			}
		}
	}
 
	return ans
}
 
func dfs(i, j int) {
	if i < 0 || i >= n || j < 0 || j >= m || theGrid[i][j] != '1' {
		return
	}
 
	// 感染
	theGrid[i][j] = '2'
	dfs(i - 1, j)
	dfs(i, j - 1)
	dfs(i + 1, j)
	dfs(i, j + 1)
}

复杂度

  • 时间复杂度：，且常数非常好
  • 空间复杂度：

题目2.被围绕的区域

题目描述

给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' ，找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。

提示：

  • m == board.length
  • n == board[i].length
  • 1 <= m, n <= 200
  • board[i][j] 为 'X' 或 'O'

测试链接

130.被围绕的区域

思路

先遍历四条边，填充所有 'O'（未被 'X' 围绕的区域），再遍历整个矩阵将 'O' 改成 'X'（被 'X' 围绕的区域），最后将之前填充的部分改回 'O'

答案

var (
	n        int
	m        int
	theBoard [][]byte
)
 
func solve(board [][]byte) {
	n = len(board)
	m = len(board[0])
	theBoard = board
	for i := 0; i < n; i++ {
		if board[i][0] == 'O' {
			dfs(i, 0)
		}
		if board[i][m-1] == 'O' {
			dfs(i, m-1)
		}
	}
	for j := 1; j < m-1; j++ {
		if board[0][j] == 'O' {
			dfs(0, j)
		}
		if board[n-1][j] == 'O' {
			dfs(n-1, j)
		}
	}
 
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			if board[i][j] == 'O' {
				board[i][j] = 'X'
			} else if board[i][j] == 0 {
				board[i][j] = 'O'
			}
		}
	}
}
 
func dfs(i, j int) {
	if i < 0 || i == n || j < 0 || j == m || theBoard[i][j] != 'O' {
		return
	}
 
	theBoard[i][j] = 0
	dfs(i, j-1)
	dfs(i, j+1)
	dfs(i-1, j)
	dfs(i+1, j)
}

题目3.最大人工岛

题目描述

给你一个大小为 n x n 二进制矩阵 grid 。最多 只能将一格 0 变成 1 。

返回执行此操作后，grid 中最大的岛屿面积是多少？

岛屿 由一组上、下、左、右四个方向相连的 1 形成。

提示：

  • n == grid.length
  • n == grid[i].length
  • 1 <= n <= 500
  • grid[i][j] 为 0 或 1

测试链接

827.最大人工岛

答案

var (
	n       int
	theGrid [][]int
	sizes   []int
	visited []bool
)
 
func largestIsland(grid [][]int) int {
	n = len(grid)
	theGrid = grid
	id := 2
 
	// 填充
	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			if grid[i][j] == 1 {
				dfs(i, j, id)
				id++
			}
		}
	}
 
	// 记录每个岛屿的大小
	// 将答案设为最大的岛屿
	sizes = make([]int, id)
	ans := 0
	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			if grid[i][j] > 1 {
				sizes[grid[i][j]]++
				ans = max(ans, sizes[grid[i][j]])
			}
		}
	}
 
	// 讨论所有的 0，变成 1，能带来的最大岛的大小
	visited = make([]bool, id)
	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			if grid[i][j] != 0 {
				continue
			}
			ans = max(ans, calcArea(i, j))
		}
	}
 
	return ans
}
 
func dfs(i, j, id int) {
	if i < 0 || i == n || j < 0 || j == n || theGrid[i][j] != 1 {
		return
	}
 
	theGrid[i][j] = id
	dfs(i, j-1, id)
	dfs(i, j+1, id)
	dfs(i-1, j, id)
	dfs(i+1, j, id)
}
 
func calcArea(i, j int) int {
	ans := 1 // 当前位置面积
	up := 0
	down := 0
	left := 0
	right := 0
	if i > 0 {
		up = theGrid[i-1][j]
	}
	if i+1 < n {
		down = theGrid[i+1][j]
	}
	if j > 0 {
		left = theGrid[i][j-1]
	}
	if j+1 < n {
		right = theGrid[i][j+1]
	}
	visited[up] = true
	ans += sizes[up]
	if !visited[down] {
		visited[down] = true
		ans += sizes[down]
	}
	if !visited[left] {
		visited[left] = true
		ans += sizes[left]
	}
	if !visited[right] {
		visited[right] = true
		ans += sizes[right]
	}
	visited[up] = false
	visited[down] = false
	visited[left] = false
	visited[right] = false
	return ans
}

题目4.打砖块

题目描述

有一个 m x n 的二元网格 grid ，其中 1 表示砖块，0 表示空白。砖块 稳定（不会掉落）的前提是：

  • 一块砖直接连接到网格的顶部，或者
  • 至少有一块相邻（4 个方向之一）砖块 稳定 不会掉落时

给你一个数组 hits ，这是需要依次消除砖块的位置。每当消除 hits[i] = (rowi, coli) 位置上的砖块时，对应位置的砖块（若存在）会消失，然后其他的砖块可能因为这一消除操作而 掉落 。一旦砖块掉落，它会 立即 从网格 grid 中消失（即，它不会落在其他稳定的砖块上）。

返回一个数组 result ，其中 result[i] 表示第 i 次消除操作对应掉落的砖块数目。

注意，消除可能指向是没有砖块的空白位置，如果发生这种情况，则没有砖块掉落。

提示：

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 200
  • grid[i][j] 为 0 或 1
  • 1 <= hits.length <= 4 * 10^4
  • hits[i].length == 2
  • 0 <= xi <= m - 1
  • 0 <= yi <= n - 1
  • 所有 (xi, yi) 互不相同

测试链接

803.打砖块

思路

很常见的技巧：“时光倒流”

先将 hits 位置都 -1，再对天花板进行洪水填充：将 1 填充成 2

那么现在 2 的位置都是 hits 后还是有方块的位置（连上天花板的位置）

“时光倒流”：对 hits 从后往前遍历，将被消除位置恢复，恢复后该位置是 1 则说明该位置被该 hit 消除的，看下这个位置恢复后是否能连上天花板（周围有 2 或者该位置为天花板），能连上就进行洪水填充，看能将多少个 1 填充成 2，这个数目就是这个 hit 消除的

答案

var (
	n       int
	m       int
	theGrid [][]int
)
 
func hitBricks(grid [][]int, hits [][]int) []int {
	n = len(grid)
	m = len(grid[0])
	theGrid = grid
	hSize := len(hits)
	ans := make([]int, hSize)
	// 特判：只有天花板一层，不会掉落砖块
	if n == 1 {
		return ans
	}
	// 将消除的位置都 -1
	for _, hit := range hits {
		grid[hit[0]][hit[1]]--
	}
	// 将天花板洪水填充
	for j := 0; j < m; j++ {
		dfs(0, j)
	}
	// “时光倒流”：从后往前消除砖块
	for k := hSize - 1; k >= 0; k-- {
		i := hits[k][0]
		j := hits[k][1]
		grid[i][j]++
		if worth(i, j) {
			ans[k] = dfs(i, j) - 1
		}
	}
	return ans
}
 
// 从 (i, j) 格子出发，遇到 1 就感染成 2
// 返回新增了几个 2
func dfs(i, j int) int {
	if i < 0 || i == n || j < 0 || j == m || theGrid[i][j] != 1 {
		return 0
	}
	theGrid[i][j] = 2
	return 1 + dfs(i, j+1) + dfs(i, j-1) + dfs(i+1, j) + dfs(i-1, j)
}
 
func worth(i, j int) bool {
	// 当前位置恢复了还是没有砖块，说明一开始就没有砖块
	if theGrid[i][j] != 1 {
		return false
	}
	return i == 0 || // 当前位置是天花板
		(i > 0 && theGrid[i-1][j] == 2) ||
		(i < n-1 && theGrid[i+1][j] == 2) ||
		(j > 0 && theGrid[i][j-1] == 2) ||
		(j < m-1 && theGrid[i][j+1] == 2)
}

Graph View

Backlinks