Understanding the DFS portion of Number of Islands in Kotlin-CodePudding

Here's the question: "Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 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

Example 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 "

So this was an answer I saw for the question "Number of Islands". I get most of the code except for the last part of it (the directional recursion part)

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)
    }

My question is what is going on in that part? Is the recursive call accounting for all sides of the 2D array surrounding the given char? Or is it something else entirely? Any help is appreciated. Thank You.

CodePudding user response：

The nested loops in numIslands() identify one cell from each island, and then call dfs() to remove that whole island from the grid. (So that the next land cell it finds will be a different island, and it's counting whole islands.)

dfs() works by setting the given cell to 0 (water), and then recursively looking at the four adjacent cells. (Which then go on to remove their adjacent cells, and so on, sweeping outward until it has removed the entire island.) The clever bit there is that the if stops it when it hits water (or the edge of the grid) — which means that although it will revisit cells it has already visited, by that point they'll be water, and so it'll ignore them and not keep going over the same cells endlessly.

(Whenever you write recursive code, you always need to be thinking about how it terminates — if not, there's a real risk that it won't! In this case, recursion only happens for cells that were land, and only after setting them to water. Since the number of land cells is always reducing, and since it can't go below zero, it's guaranteed to terminate after a finite number of steps.)

dfs() is not a very helpful name! If you were writing this code, I'd suggest renaming it to something more meaningful, such as removeIslandAt(). (I'd also suggest making it an extension function on Array<CharArray.)

To understand code like this, I always find it useful to be able to see what's going on. You might write a little function to display the current state of the grid; then you could call that at the start of dfs() (along with displaying the i and j co-ordinates). That should make it much clearer how it works. (If you really wanted, you could make an animation out of it, which would be clearer still!)