Solution to Leetcode 200 Number of Islands

soln_lc200.py

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        # dfs, recurssion
        if not grid:
            return 0 
        
        rows, cols = len(grid), len(grid[0])
        result = 0 

        def dfs(r, c):
            if r<0 or c<0 or r>rows-1 or c>cols-1 or grid[r][c] == '0':
                return 
            # mark as visited
            grid[r][c] = '0'
            # keep marking up, left, right, down
            dfs(r+1, c)
            dfs(r, c-1)
            dfs(r, c+1)
            dfs(r-1, c)
        
        for r in range(0, rows):
            for c in range(0, cols):
                if grid[r][c] == '1':
                    result += 1
                    dfs(r, c)
        
        return result 

dfs() can also be:

def dfs(r, c):
      if (r<0 or c<0 or r>=rows or c>=cols or grid[r][c]=='0'):
          return 
      grid[r][c] = '0'
      # up, down, left, right
      dfs(r-1, c)
      dfs(r+1, c)
      dfs(r, c-1)
      dfs(r, c+1)

Note that dfs(r-1, c) will propagate to dfs(r-2,c) ...

dfs(r+1,c) will be executed only if all four directions of (r-1,c) are out of bounds or already "0".