Daily Study
更新: 10/5/2025 字数: 0 字 时长: 0 分钟
Daily Plan
#todo
- [ ]
网格类问题的DFS遍历方法
网格问题是由 m×n 个小方格组成一个网格，每个小方格与其上下左右四个方格认为是相邻的，要在这样的网格上进行某种搜索。
岛屿问题是一类典型的网格问题。每个格子中的数字可能是 0 或者 1。我们把数字为 0 的格子看成海洋格子，数字为 1 的格子看成陆地格子，这样相邻的陆地格子就连接成一个岛屿。 
在这样一个设定下，就出现了各种岛屿问题的变种，包括岛屿的数量、面积、周长等。不过这些问题，基本都可以用 DFS 遍历来解决。
DFS的基本要素：
- 终止条件：二叉树一般是
root == null，网格上的DFS类似，也就是数组下标在界限内 - 访问相邻节点：二叉树是左右子树，网格就是能够访问的方向
DFS要避免重复访问：标记已经访问过的格子
- 0 —— 海洋格子
- 1 —— 陆地格子（未遍历过）
- 2 —— 陆地格子（已遍历过）
go
var dfs func ([][]byte, int, int)
dfs = func(grid [][]byte, r, c int) {
if !inArea(grid, r, c){
return
}
if grid[r][c] != '1' {
return
}
grid[r][c] = 2
dfs(grid, r - 1, c)
dfs(grid, r + 1, c)
dfs(grid, r, c - 1)
dfs(grid, r, c + 1)
}