0200. 岛屿数量

0200. 岛屿数量 #

  • 标签:搜索
  • 难度:中等

题目大意 #

给你一个由 ‘1’(陆地)和 ‘0’(水)组成的的二维网格 grid

要求:计算网格中岛屿的数量。

  • 岛屿总是被水包围,并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

  • 此外,你可以假设该网格的四条边均被水包围。

解题思路 #

如果把上下左右相邻的字符 ‘1’ 看做是 1 个连通块,这道题的目的就是求解一共有多少个连通块。

使用深度优先搜索或者广度优先搜索都可以。

以深度优先搜索为例。遍历 grid 。对于每一个字符为 ‘1’ 的元素,遍历其上下左右四个方向,并将该字符置为 0,保证下次不会被重复遍历。对于 (i, j) 位置的元素来说,递归遍历的位置就是 (i - 1, j)(i, j - 1)(i + 1, j)(i, j + 1) 四个方向。每次遍历到底,统计数记录一次。最终统计出深度优先搜索的次数就是我们要求的岛屿数量。

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def dfs(self, grid, i, j):
        n = len(grid)
        m = len(grid[0])
        if i < 0 or i >= n or j < 0 or j >= m or grid[i][j] == '0':
            return 0
        grid[i][j] = '0'
        self.dfs(grid, i+1, j)
        self.dfs(grid, i, j+1)
        self.dfs(grid, i-1, j)
        self.dfs(grid, i, j-1)

    def numIslands(self, grid: List[List[str]]) -> int:
        count = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == '1':
                    self.dfs(grid, i, j)
                    count += 1
        return count
本站总访问量  次  |  您是本站第  位访问者