leetcode

Leetcode submissions
git clone git://git.laack.co/leetcode.git
Log | Files | Refs | README

number-of-islandsV1.py (970B)

      1 # loop over the entire grid
      2 # if current_val == 1:
      3 # bfs to find connected component
      4 # when performing bfs, set each position to -1
      5 # increment connected component counter
      6 # return # of connected components
      7 
      8 
      9 class Solution:
     10     def numIslands(self, grid: List[List[str]]) -> int:
     11 
     12         count = 0
     13 
     14         for y in range(len(grid)):
     15             for x in range(len(grid[y])):
     16                 if grid[y][x] == "1":
     17                     mark_cc(y, x, grid)
     18                     count += 1
     19         return count
     20 
     21 
     22 def mark_cc(y_pos, x_pos, board):
     23 
     24     # visited already or water
     25     if board[y_pos][x_pos] != "1":
     26         return
     27 
     28     board[y_pos][x_pos] = "-1"
     29 
     30     # left
     31     if x_pos > 0:
     32         mark_cc(y_pos, x_pos - 1, board)
     33 
     34     # right
     35     if x_pos < len(board[0]) - 1:
     36         mark_cc(y_pos, x_pos + 1, board)
     37 
     38     # up
     39     if y_pos > 0:
     40         mark_cc(y_pos - 1, x_pos, board)
     41 
     42     # down
     43     if y_pos < len(board) - 1:
     44         mark_cc(y_pos + 1, x_pos, board)