Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
类似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

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理