Advertisement
rishu110067

Untitled

Jan 27th, 2022
1,034
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. from collections import deque
  2. def count_islands(matrix):
  3.     """
  4.    Args:
  5.     matrix(list_list_int32)
  6.    Returns:
  7.     int32
  8.    """
  9.     # Write your code here.
  10.     row = len(matrix)
  11.     col = len(matrix[0])
  12.     visited = set()
  13.     island = 0
  14.     # extension => traverse the matrix: 1) land 2) in bounds 3) up down left right top-left top-right bottom-left bottom-right
  15.     def get_neighbors(i, j):
  16.         neighbors = []
  17.         # up
  18.         if i-1 >= 0 and matrix[i-1][j] == 1:
  19.             neighbors.append((i-1, j)) #query
  20.         # down
  21.         if i+1 < row and matrix[i+1][j] == 1:
  22.             neighbors.append((i+1, j)) #query
  23.         # left
  24.         if j-1 >= 0 and matrix[i][j - 1] == 1:
  25.             neighbors.append((i, j-1)) #query
  26.         # right
  27.         if j+1 < col and matrix[i][j + 1] == 1:
  28.             neighbors.append((i, j+1)) #query
  29.         #top-left
  30.         if i-1 >= 0 and j-1 >= 0 and matrix[i-1][j-1] == 1:
  31.             neighbors.append((i-1, j-1)) #query
  32.         #top-right
  33.         if i-1 >= 0 and j+1 < col and matrix[i-1][j+1] == 1:
  34.             neighbors.append((i-1, j+1)) #query
  35.         #bottom-left
  36.         if i+1 < row and j-1 >= 0 and matrix[i+1][j-1] == 1:
  37.             neighbors.append((i+1, j-1)) #query
  38.         #bottom-right
  39.         if i+1 < row and j+1 < col and matrix[i+1][j+1] == 1:
  40.             neighbors.append((i+1, j+1)) #query
  41.        
  42.         return neighbors
  43.     # bfs
  44.     def bfs(i, j):
  45.         visited.add((i, j))
  46.         q = deque()
  47.         q.append((i, j))
  48.         while q:
  49.             c_i, c_j = q.popleft()
  50.             for n_i, n_j in get_neighbors(c_i, c_j):
  51.                 if (n_i, n_j) not in visited: # query!
  52.                     visited.add((n_i, n_j))
  53.                     q.append((n_i, n_j))
  54.         return
  55.    
  56.        
  57.     # outer loop
  58.     for i in range(row):
  59.         for j in range(col):
  60.             if (i,j) not in visited and matrix[i][j] == 1:
  61.                 bfs(i, j)
  62.                 island += 1
  63.            
  64.     return island
  65.  
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement