Kotlin版岛屿数量问题中DFS递归部分的原理解析

给定一个m×n的二维二进制网格grid，其中'1'代表陆地，'0'代表水域，返回岛屿的数量。岛屿由水平或垂直相邻的陆地连接而成，且网格四周均被水域环绕。

示例1 #

Input: grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]

Output: 1

示例2 #

Input: grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]

Output: 3

代码与疑问 #

以下是该问题的一份Kotlin实现代码，我理解大部分逻辑，但对其中DFS函数的方向递归部分存在疑问：

fun numIslands(grid: Array<CharArray>): Int {
        var count = 0
        
        for (i in grid.indices){
            for (j in grid[0].indices){
                if(grid[i][j] == '1'){
                    dfs(grid, i, j)
                    count++
                }
            }
        }
        return count
        
    }
    
    private fun dfs(grid: Array<CharArray>, i: Int, j: Int){
        if(i < 0 || j < 0 || i >= grid.size|| j >= grid[0].size || grid[i][j] == '0'){
            return
        }
        
        //directional recursion
        grid[i][j] = '0'
        dfs(grid, i + 1, j)
        dfs(grid, i, j + 1)
        dfs(grid, i - 1, j)
        dfs(grid, i, j - 1)
    }

我的问题是：这部分递归调用的作用是什么？是否是遍历当前字符在二维网格中的上下左右所有相邻区域？还是存在其他逻辑？希望得到解答，谢谢。

解答 #

这四个递归调用就是遍历当前位置的上下左右四个相邻区域，核心目的是把当前所在的整个岛屿全部"标记为水域"，避免后续重复计数。

具体逻辑拆解：

• 当找到一块陆地（'1'）时，先把当前位置改成'0'（相当于标记已访问，防止重复处理）
• 接着递归检查上下左右四个方向：如果相邻位置是陆地，就继续执行"标记为水域+递归检查相邻"的操作
• 这样整个连通的陆地都会被改成'0'，后续外层循环遍历到这些位置时，只会看到'0'，不会再触发计数，保证每个岛屿只被统计一次

比如示例1中左上角的'1'，调用DFS后，所有连通的'1'都会被置为'0'，外层循环后续遍历这些位置时不会再计数，所以最终只统计1个岛屿。

内容的提问来源于stack exchange，提问作者OEThe11