200.Number of Islands
My code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
from collections import deque
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
num_of_island = 0
col = len(grid)
row = len(grid[0])
visited = [[False]*row for _ in range(col)]
def bfs(x,y):
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
visited[x][y] = True
queue = deque()
queue.append((x,y))
while queue:
cur_x,cur_y = queue.popleft()
if i in range(4):
next_x = cur_x + dx[i]
next_y = cur_y + dy[i]
if next_x >= 0 and next_x < m and next_y >= 0 and next_y < n:
if grid[next_x][next_y] == "1" and not visited[next_x][next_y]:
visited[next_x][next_y] = True
queue.append((next_x,next_y))
for i in range(m):
for j in range(n):
if grid[i][j] == "1" and not visited[i][j]:
bfs(i,j)
num_of_island += 1
return num_of_island
Answer
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
directions = [(0, 1), (1, 0), (-1, 0), (0, -1)]
ROWS = len(grid)
COLS = len(grid[0])
def bfs(i, j):
q = deque()
q.append((i, j))
while q:
currRow, currCol = q.popleft()
for dr, dc in directions:
r = currRow + dr
c = currCol + dc
if r in range(ROWS) and c in range(COLS) and grid[r][c] == '1':
grid[r][c] = '-1'
q.append((r, c))
return grid
count = 0
for i in range(ROWS):
for j in range(COLS):
if grid[i][j] == '1':
bfs(i, j)
count += 1
return count