[200][中等][DFS] 岛屿数量

题目描述

200. 岛屿数量

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

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

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

示例 1:

输入:
[
['1','1','1','1','0'],
['1','1','0','1','0'],
['1','1','0','0','0'],
['0','0','0','0','0']
]
输出: 1

示例 2:

输入:
[
['1','1','0','0','0'],
['1','1','0','0','0'],
['0','0','1','0','0'],
['0','0','0','1','1']
]
输出: 3
解释: 每座岛屿只能由水平和/或竖直方向上相邻的陆地连接而成。

解题思路

0为水, 1为陆地. 我们从一个陆地开始, 向四周搜索, 找到该岛屿的所有连接的陆地, 然后继续搜索下一个岛屿.

为了进行剪枝, 我们将搜索过的地方标记为2, 代表搜索过的陆地, 在进行DFS时遇到越界, 水域0, 以及搜索过的陆地2时进行剪枝. 在对所有点进行遍历, 找到一个岛屿的起始搜索位置时, 要跳过0和2.

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if len(grid) == 0:
            return 0
        n, m = len(grid), len(grid[0])

        def dfs(i, j):
            if not 0 <= i < n or not 0 <= j < m:
                return
            if grid[i][j] in ('0', '2'):
                return

            grid[i][j] = '2'
            dfs(i - 1, j)
            dfs(i + 1, j)
            dfs(i, j - 1)
            dfs(i, j + 1)

        count = 0
        for i in range(n):
            for j in range(m):
                if grid[i][j] == '1':
                    count += 1
                    dfs(i, j)
        return count