-
Notifications
You must be signed in to change notification settings - Fork 4
/
NumberOfIslands.py
32 lines (32 loc) · 1.24 KB
/
NumberOfIslands.py
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
from collections import deque
class Solution:
def numIslands(self, grid) -> int:
if not grid:
return 0
r = len(grid)
c = len(grid[0])
queue = deque()
islands = 0
for i in range(r):
for j in range(c):
if grid[i][j] == '1':
islands += 1
grid[i][j] = '0'
queue.append([i, j])
while queue:
el = queue.popleft()
rs = el[0]
cs = el[1]
if rs - 1 >= 0 and grid[rs-1][cs] == '1':
queue.append([rs-1, cs])
grid[rs-1][cs] = '0'
if rs + 1 < r and grid[rs+1][cs] == '1':
queue.append([rs+1, cs])
grid[rs+1][cs] = '0'
if cs - 1 >= 0 and grid[rs][cs-1] == '1':
queue.append([rs, cs-1])
grid[rs][cs-1] = '0'
if cs + 1 < c and grid[rs][cs+1] == '1':
queue.append([rs, cs+1])
grid[rs][cs+1] = '0'
return islands