old_contents: # Time:  O(m * n)
  # Space: O(m * n)
  #
  # Given a 2d grid map of '1's (land) and '0's (water), count 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:
  #
  # 11110
  # 11010
  # 11000
  # 00000
  # Answer: 1
  #
  # Example 2:
  #
  # 11000
  # 11000
  # 00100
  # 00011
  # Answer: 3
  #
  
  class Solution:
      # @param {boolean[][]} grid a boolean 2D matrix
      # @return {int} an integer
      def numIslands(self, grid):
          if not grid:
              return 0
      
          row = len(grid)
          col = len(grid[0])
          used = [[False for j in xrange(col)] for i in xrange(row)]
      
          count = 0
          for i in xrange(row):
              for j in xrange(col):
                  if grid[i][j] == 1 and not used[i][j]:
                      self.dfs(grid, used, row, col, i, j)
                      count += 1
          return count
  
      def dfs(self, grid, used, row, col, x, y):
          if grid[x][y] == 0 or used[x][y]:
              return
          used[x][y] = True
      
          if x != 0:
              self.dfs(grid, used, row, col, x - 1, y)
          if x != row - 1:
              self.dfs(grid, used, row, col, x + 1, y)
          if y != 0:
              self.dfs(grid, used, row, col, x, y - 1)
          if y != col - 1:
              self.dfs(grid, used, row, col, x, y + 1)
  
new_contents: # Time:  O(m * n)
  # Space: O(m * n)
  #
  # Given a 2d grid map of '1's (land) and '0's (water), count 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:
  #
  # 11110
  # 11010
  # 11000
  # 00000
  # Answer: 1
  #
  # Example 2:
  #
  # 11000
  # 11000
  # 00100
  # 00011
  # Answer: 3
  #
  
  class Solution:
      # @param {boolean[][]} grid a boolean 2D matrix
      # @return {int} an integer
      def numIslands(self, grid):
          if not grid:
              return 0
      
          row = len(grid)
          col = len(grid[0])
          used = [[False for j in xrange(col)] for i in xrange(row)]
      
          count = 0
          for i in xrange(row):
              for j in xrange(col):
                  if grid[i][j] == '1' and not used[i][j]:
                      self.dfs(grid, used, row, col, i, j)
                      count += 1
          return count
  
      def dfs(self, grid, used, row, col, x, y):
          if grid[x][y] == '0' or used[x][y]:
              return
          used[x][y] = True
      
          if x != 0:
              self.dfs(grid, used, row, col, x - 1, y)
          if x != row - 1:
              self.dfs(grid, used, row, col, x + 1, y)
          if y != 0:
              self.dfs(grid, used, row, col, x, y - 1)
          if y != col - 1:
              self.dfs(grid, used, row, col, x, y + 1)
  
subject: Update number-of-islands.py