forked from super30admin/DFS-2
-
Notifications
You must be signed in to change notification settings - Fork 0
/
numberOfIslands.py
31 lines (31 loc) · 1.09 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
"""
Time complexity: O(M * N)
Space complexity: O( sqrt(M^2 + N^2))
Compiled on leetcode: Yes
Difficulties faced: No
"""
from collections import deque
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
if not grid:
return 0
islandCount = 0
m = len(grid)
n = len(grid[0])
dirs = ((1,0), (-1,0), (0, -1), (0, 1))
queue = deque()
for i in range(m):
for j in range(n):
if grid[i][j] == '1':
queue.append((i,j))
while queue:
currentIndex = queue.popleft()
grid[currentIndex[0]][currentIndex[1]] = '0'
for dir in dirs:
r = dir[0] + currentIndex[0]
c = dir[1] + currentIndex[1]
if r >= 0 and r < m and c >= 0 and c < n and grid[r][c] == '1':
grid[r][c] = '0'
queue.append((r,c))
islandCount += 1
return islandCount