Posted on 2023-04-07 19:23
Uriel 閱讀(68)
評論(0) 編輯 收藏 引用 所屬分類:
搜索 、
閑來無事重切Leet Code
類似1254題，給定一個0-1矩陣，1代表海島0代表水，本題求問有幾個格點是海中的陸地格點（邊緣的不算）
同樣，DFS求連通分支個數，如果不是位于邊緣的聯通分支，則ans加上此次DFS到達過的格點數
1 #1020
2 #Runtime: 691 ms (Beats 37.84%)
3 #Memory: 75.3 MB (Beats 20.27%)
4
5 class Solution(object):
6 def numEnclaves(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] = 0
17 self.tp += 1
18 for dx, dy in self.dir:
19 tx = x + dx
20 ty = y + dy
21 if 0 <= tx < n and 0 <= ty < m and grid[tx][ty]:
22 DFS(tx, ty)
23 elif tx < 0 or ty < 0 or tx >= n or ty >= m:
24 self.fg = False
25
26
27 self.vis = [[0] * m for _ in range(n)]
28 self.ans = 0
29 for i in range(1, n - 1):
30 for j in range(1, m - 1):
31 if grid[i][j] == 1:
32 self.fg = True
33 self.tp = 0
34 DFS(i, j)
35 if self.fg == True:
36 self.ans += self.tp
37 return self.ans