当前位置：网站首页>leetcode: 200. 岛屿数量

leetcode: 200. 岛屿数量

2022-08-02 10:24:00 【uncle_ll】

200. 岛屿数量

来源：力扣（LeetCode）

链接: https://leetcode.cn/problems/number-of-islands/

给你一个由 '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

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j] 的值为 '0' 或 '1'

解法

总的思想是进行遍历，如果遍历到陆地，岛屿数+1，并改变该岛屿的值为‘0’或者设置访问状态为已访问，再基于该陆地，向四周进行扩散，将与之相岭的陆地设置为‘0’或者设置访问状态为已访问

BFS：用队列进行存储该陆地，并进行四个方向的遍历，如果后续有陆地，进入队列，直到队列为空
DFS：用递归的方式进行四个方向的遍历

代码实现

BFS

python实现

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid or len(grid[0]) == 0:
            return 0
        
        rows = len(grid)
        cols = len(grid[0])
        count = 0
        dr = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        for x in range(rows):
            for y in range(cols):
                if grid[x][y] == '1':
                    count += 1
                    queue = [(x, y)]
                    grid[x][y] = 0
                    while queue:
                        cx, cy = queue.pop(0)
                        for dx, dy in dr:
                            nx = cx + dx
                            ny = cy + dy
                            if 0<= nx < rows and 0 <= ny < cols and grid[nx][ny] == '1':
                                queue.append((nx, ny))
                                grid[nx][ny] = '0'
        return count

c++实现

class Solution {
    
public:
    int numIslands(vector<vector<char>>& grid) {
    
        int rows = grid.size();
        if (rows == 0)
            return 0;
        
        int cols = grid[0].size();
        if (cols == 0)
            return 0;
        vector<pair<int, int>> dr;
        dr = {
    {
    1, 0}, {
    -1, 0}, {
    0, 1}, {
    0, -1}};
        int count = 0;
        for (int i=0; i< rows; i++) {
    
            for (int j=0; j< cols; j++) {
    
                if (grid[i][j] == '1') {
    
                    count++;
                    grid[i][j] = 0;
                    queue<pair<int, int>> q;
                    q.push({
    i, j});
                    while (!q.empty()) {
    
                        auto cur = q.front();
                        q.pop();
                        int x = cur.first;
                        int y = cur.second;
                        for (auto d: dr) {
    
                            int dx = d.first;
                            int dy = d.second;
                            int nx = x + dx;
                            int ny = y + dy;
                            if (nx >= 0 && nx < rows && ny >= 0 && ny < cols && grid[nx][ny] == '1'){
    
                                q.push({
    nx, ny});
                                grid[nx][ny] = '0';
                            }

                        }
                    }
                }
            }
        }
        return count;
    }
};

复杂度分析

时间复杂度： $O (MN)$ M和N分别为行数和列数
空间复杂度： $O (min (M, N))$ 在最坏情况下，整个网格均为陆地，队列的大小可以达到 $\min(M, N)$ 。

DFS

python实现

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid or len(grid[0]) == 0:
            return 0
        
        rows = len(grid)
        cols = len(grid[0])
        count = 0
        dr = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        for x in range(rows):
            for y in range(cols):
                if grid[x][y] == '1':
                    count += 1
                    queue = [(x, y)]
                    grid[x][y] = 0
                    while queue:
                        cx, cy = queue.pop(0)
                        for dx, dy in dr:
                            nx = cx + dx
                            ny = cy + dy
                            if 0<= nx < rows and 0 <= ny < cols and grid[nx][ny] == '1':
                                queue.append((nx, ny))
                                grid[nx][ny] = '0'
        return count

c++实现

class Solution {
    
private:
    void dfs(vector<vector<char>>& grid, int r, int c) {
    
        int nr = grid.size();
        int nc = grid[0].size();

        grid[r][c] = '0';
        if (r - 1 >= 0 && grid[r-1][c] == '1') dfs(grid, r - 1, c);
        if (r + 1 < nr && grid[r+1][c] == '1') dfs(grid, r + 1, c);
        if (c - 1 >= 0 && grid[r][c-1] == '1') dfs(grid, r, c - 1);
        if (c + 1 < nc && grid[r][c+1] == '1') dfs(grid, r, c + 1);
    }

public:
    int numIslands(vector<vector<char>>& grid) {
    
        int nr = grid.size();
        if (!nr) return 0;
        int nc = grid[0].size();

        int num_islands = 0;
        for (int r = 0; r < nr; ++r) {
    
            for (int c = 0; c < nc; ++c) {
    
                if (grid[r][c] == '1') {
    
                    ++num_islands;
                    dfs(grid, r, c);
                }
            }
        }

        return num_islands;
    }
};