Uriel's Corner

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

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