leetcode每日一题No.200岛屿数量

200.岛屿数量

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

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

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

示例 1：

输入：grid = [
[‘1’,’1’,’1’,’1’,’0’],
[‘1’,’1’,’0’,’1’,’0’],
[‘1’,’1’,’0’,’0’,’0’],
[‘0’,’0’,’0’,’0’,’0’]
]
输出：1
示例 2：

输入：grid = [
[‘1’,’1’,’0’,’0’,’0’],
[‘1’,’1’,’0’,’0’,’0’],
[‘0’,’0’,’1’,’0’,’0’],
[‘0’,’0’,’0’,’1’,’1’]
]
输出：3

思路

用深搜/广搜从小岛的某一点扩散出去把每个部分都置为0，完成这样的一次操作就给岛屿计数器更新+1，然后遍历一遍即可

python实现

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        m = len(grid)
        n = len(grid[0])
        ans = 0
        def expand(y:int , x:int) :
        #递归深搜,输入一个坐标然后把整个小岛都扩散一遍，一边扩散一边把1置0
            # 边界条件
            if y < 0 or y > m - 1 or x < 0 or x > n - 1 or grid[y][x] == "0":
                return  
            else:
                grid[y][x] = "0"
                expand(y-1,x)
                expand(y+1,x)
                expand(y,x-1)
                expand(y,x+1)
        for i in range(m):
            for j in range(n):
                if grid[i][j] == "1":
                    expand(i,j)
                    ans += 1
        return ans

cpp实现

# 基本上和python实现思路相同，只是我为了熟悉写cpp所以又写了一遍
class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        int ans = 0;

        auto expand = [&](this auto&& expand, int y, int x) {
            if (y < 0 || y >= m || x < 0 || x >= n || grid[y][x] == '0')
                return;

            grid[y][x] = '0';
            expand(y - 1, x);
            expand(y + 1, x);
            expand(y, x - 1);
            expand(y, x + 1);
        };

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == '1') {
                    expand(i, j);
                    ++ans;
                }
            }
        }
        return ans;
    }
};