leetcode: 200. Number of islands

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'

解法

The general idea is to traverse,如果遍历到陆地,岛屿数+1,and change the value of the island to ‘0’Or set the access status to Accessed,based on the land,Spread around,Set the land with the ridge to ‘0’Or set the access status to Accessed

• BFS：The land is stored with a queue,And traverse in four directions,If there is land in the future,进入队列,直到队列为空
• DFS： Traverse in four directions recursively

代码实现

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;
    }
};

复杂度分析

• 时间复杂度： $O(MN)$ M和N分别为行数和列数
• 空间复杂度： $O(MN)$ M和N分别为行数和列数

参考

• https://leetcode.cn/problems/number-of-islands/solution/dao-yu-shu-liang-by-leetcode/
• https://leetcode.cn/problems/number-of-islands/solution/dao-yu-lei-wen-ti-de-tong-yong-jie-fa-dfs-bian-li-/