Posted on 2023-04-06 19:31
Uriel 閱讀(40)
評論(0) 編輯 收藏 引用 所屬分類:
搜索 、
閑來無事重切Leet Code
給定一個0-1矩陣，0代表海島1代表水，問整個矩陣里有幾片陸地（邊緣的不算）
DFS求連通分支個數
1 #1254
2 #Runtime: 103 ms (Beats 49.4%)
3 #Memory: 14 MB (Beats 37.50%)
4
5 class Solution(object):
6 def closedIsland(self, grid):
7 """
8 :type grid: List[List[int]]
9 :rtype: int
10 """
11 self.dir = [[-1, 0], [1, 0], [0, -1], [0, 1]]
12 n = len(grid)
13 m = len(grid[0])
14
15 def DFS(x, y):
16 grid[x][y] = 1
17 for dx, dy in self.dir:
18 tx = x + dx
19 ty = y + dy
20 if 0 <= tx < n and 0 <= ty < m and not grid[tx][ty]:
21 DFS(tx, ty)
22 elif tx < 0 or ty < 0 or tx >= n or ty >= m:
23 self.fg = False
24
25
26 self.vis = [[0] * m for _ in range(n)]
27 ans = 0
28 for i in range(1, n - 1):
29 for j in range(1, m - 1):
30 if grid[i][j] == 0:
31 self.fg = True
32 DFS(i, j)
33 if self.fg == True:
34 ans += 1
35 return ans