-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathnumIslands.py
More file actions
61 lines (56 loc) · 2.15 KB
/
Copy pathnumIslands.py
File metadata and controls
61 lines (56 loc) · 2.15 KB
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#!/user/bin/env python3
# coding=utf-8
"""
@project : algorithmPython
@ide : PyCharm
@file : numIslands
@author : illusion
@desc : 200. 岛屿数量 https://leetcode-cn.com/problems/number-of-islands/
@create : 2021/6/5
"""
class Solution:
def numIslands(self, grid: [[str]]) -> int:
num = 0
visited = [[False for n in range(len(grid[m]))] for m in range(len(grid))]
for m in range(len(grid)):
for n in range(len(grid[m])):
value = grid[m][n]
if visited[m][n] or value == '0':
continue
num += 1
self.dfs_mark_visit(grid, m, n, visited)
return num
def dfs_mark_visit(self, grid: [[str]], m: int, n: int, visited: [[int]]):
if m < 0 or m >= len(grid) or n < 0 or n >= len(grid[m]) or visited[m][n] or grid[m][n] == '0':
return
visited[m][n] = True
self.dfs_mark_visit(grid, m - 1, n, visited)
self.dfs_mark_visit(grid, m + 1, n, visited)
self.dfs_mark_visit(grid, m, n - 1, visited)
self.dfs_mark_visit(grid, m, n + 1, visited)
def numIslands_length(self, grid: [[str]]) -> int:
if not len(grid) or not len(grid[0]):
return 0
num = 0
visited = [[False for n in range(len(grid[m]))] for m in range(len(grid))]
for m in range(len(grid)):
for n in range(len(grid[m])):
value = grid[m][n]
if visited[m][n] or value == '0':
continue
num += 1
stack = [(m, n)]
while len(stack):
m1, n1 = stack.pop()
if visited[m1][n1] or grid[m1][n1] == '0':
continue
visited[m1][n1] = True
if m1 > 0:
stack.append((m1 - 1, n1))
if m1 < len(grid) - 1:
stack.append((m1 + 1, n1))
if n1 > 0:
stack.append((m1, n1 - 1))
if n1 < len(grid[m1]) - 1:
stack.append((m1, n1 + 1))
return num