岛屿数量

Leetcode Link: 200. 岛屿数量 - 力扣（LeetCode）

题目

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

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

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

解法一

思路：用递归的思路来解

只需要找一个岛屿上的陆地(“1”)，然后我们通过一个函数将grid里这个岛屿变成海水，并且res+1，遍历所有的grid即可

本题的关键

1. 擦除岛屿的时候 base case 的判断
2. 如何避免重复走一个地方同时不遗漏（四个方向）

题解：

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
 
        def erase(i,j):
            if i<0 or i>len(grid)-1 or j<0 or j>len(grid[0])-1:
                return 
            if grid[i][j] == "1":
                grid[i][j] = "0"
                erase(i+1, j)
                erase(i, j+1)
                erase(i-1, j)
                erase(i, j-1)
            return 
 
        res = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == "1":
                    res += 1
                    erase(i,j)
        return res

本题避免重复的思路

本题不需要刻意避免重复。 在类似思路的回溯问题中（单词搜索），是通过定义 dict 来避免重复的。 在本题中，因为走过的”1”全部改成了”0”，因此本是上是通过判断”0”来避免重复的，不需要额外添加一个全局dict

启发和联系

本题属于岛屿问题。