题解 | #岛屿数量#

此题雷同lc的200题。

题目描述

解题思路

1. 遍历每个点，如果当前点为1，则将岛屿数量加1，并以当前点为起点进行深度优先搜索，进入递归；
2. 将所有与当前点联通的1标记为0，表示已经访问过。遍历当前点的上下左右点，如果不越界且为1，继续以当前点递归；
3. 最后返回岛屿数量。

# 判断岛屿数量
# @param grid char字符型二维数组 
# @return int整型
# 首先遍历每个点，如果当前点为1，则将岛屿数量加1，并以当前点为起点进行深度优先搜索，将所有与当前点联通的1标记为0，表示已经访问过。最后返回岛屿数量。
class Solution:
    def find(self,grid, r, c):
        # 当前的点标记为0
        grid[r][c] = 0
        # 遍历周围的点, 上下左右
        for x, y in [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)]: 
            # 如果不越界并且为1
            if 0<=x<row and 0<=y<col and grid[x][y] == '1':
                self.find(grid, x, y)

    def numIslands(self, grid: List[List[str]]) -> int:
        global row, col
        row = len(grid)
        col = len(grid[0])
        res = 0
        for i in range(row):
            for j in range(col):
                if grid[i][j] == '1':
                    res += 1
                    self.find(grid, i, j)
        return res