SHARE
TWEET

Untitled

a guest Sep 19th, 2019 82 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution:
  2.     def numIslands(self, grid: List[List[str]]) -> int:
  3.         if grid is None or len(grid) is 0:
  4.             return 0
  5.         row_count = len(grid)
  6.         col_count = len(grid[0])
  7.         visited = [[0 for _ in range(col_count)] for _ in range(row_count)]
  8.         islands = 0
  9.         for row_idx in range(len(visited)):
  10.             for col_idx in range(len(visited[row_idx])):
  11.                 if not visited[row_idx][col_idx]:
  12.                     # haven't visited this cell before
  13.                     # find current cell in original
  14.                     curr_cell = grid[row_idx][col_idx]
  15.                     if curr_cell is "1":
  16.                         # if 1, new island has been found
  17.                         islands += 1
  18.                         # now must find all connecting land elements
  19.                         lands = [(row_idx, col_idx)]
  20.                         while lands:
  21.                             curr_land = lands.pop()
  22.                             associated_row = curr_land[0]
  23.                             associated_col = curr_land[1]
  24.                             if grid[associated_row][associated_col] is "1":
  25.                                 if not visited[associated_row][associated_col]:
  26.                                     visited[associated_row][associated_col] = 1
  27.                                     # go through these neighbors and add to lands
  28.                                     look_up = associated_row - 1
  29.                                     look_down = associated_row + 1
  30.                                     look_left = associated_col - 1
  31.                                     look_right = associated_col + 1
  32.                                     if look_up >= 0 and look_up < row_count:
  33.                                         lands.append((look_up, associated_col))
  34.                                     if look_down >= 0 and look_down < row_count:
  35.                                         lands.append((look_down, associated_col))
  36.                                     if look_left >= 0 and look_left < col_count:
  37.                                         lands.append((associated_row, look_left))
  38.                                     if look_right >= 0 and look_right < col_count:
  39.                                         lands.append((associated_row, look_right))
  40.         return islands
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top