Posted on 2023-04-07 19:23
Uriel 阅读(32)
评论(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