# 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):
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!
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.