计算岛屿数量

题解思路

本题是一个典型的 连通区域个数 计算问题，可以用 深度优先搜索（DFS） 或 广度优先搜索（BFS） 解决。

方法1：深度优先搜索（DFS）

• 遍历整个网格，遇到 '1'（陆地） 时，进行 深度优先搜索，将与之相连的所有陆地标记为 '0'（水），防止重复计算。
• 递归搜索当前陆地的 上下左右 四个方向，直到整个岛屿被标记完毕。
• 继续遍历，统计岛屿数量。

时间复杂度：

• 每个网格单元最多被访问 一次，因此时间复杂度为 O(n×m)。

空间复杂度：

• 递归调用栈的深度最坏情况下为 O(n×m)（当整个网格都是陆地时）。
• 但通常情况下 O(1) 额外空间（原地修改输入网格）。

方法2：广度优先搜索（BFS）

• 遍历网格，遇到 '1'（陆地） 时，使用 队列 进行 广度优先搜索，将所有相连的陆地标记为 '0'。
• BFS 使用 队列 而不是递归，避免栈溢出问题。
• BFS 遍历四个方向，直到整个岛屿被完全标记。

时间复杂度：

• 每个网格单元最多被访问 一次，时间复杂度 O(n×m)。

空间复杂度：

• O(min(n, m))（队列在最坏情况下的最大深度）。

DFS与BFS

深度优先搜索（DFS）解法

Python 代码

class Solution:
    def numIslands(self, grid):
        if not grid or not grid[0]:
            return 0
        
        rows, cols = len(grid), len(grid[0])
        count = 0

        def dfs(r, c):
            # 边界检查 & 避免重复访问
            if r < 0 or c < 0 or r >= rows or c >= cols or grid[r][c] == '0':
                return
            # 标记访问过的陆地
            grid[r][c] = '0'
            # 递归访问上下左右
            dfs(r + 1, c)
            dfs(r - 1, c)
            dfs(r, c + 1)
            dfs(r, c - 1)

        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == '1':
                    count += 1  # 遇到新的岛屿
                    dfs(r, c)  # 深度优先搜索标记整座岛屿

        return count

# 读取输入
if __name__ == "__main__":
    n, m = map(int, input().split())
    grid = [list(input().strip()) for _ in range(n)]
    solution = Solution()
    print(solution.numIslands(grid))

Java 代码

import java.util.*;

public class Main {
    public class Solution {
        public int numIslands(char[][] grid) {
            if (grid == null || grid.length == 0) {
                return 0;
            }

            int rows = grid.length;
            int cols = grid[0].length;
            int count = 0;

            for (int r = 0; r < rows; r++) {
                for (int c = 0; c < cols; c++) {
                    if (grid[r][c] == '1') {
                        count++;
                        dfs(grid, r, c);
                    }
                }
            }
            return count;
        }

        private void dfs(char[][] grid, int r, int c) {
            if (r < 0 || c < 0 || r >= grid.length || c >= grid[0].length || grid[r][c] == '0') {
                return;
            }

            grid[r][c] = '0'; // 标记已访问
            dfs(grid, r + 1, c);
            dfs(grid, r - 1, c);
            dfs(grid, r, c + 1);
            dfs(grid, r, c - 1);
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(), m = scanner.nextInt();
        char[][] grid = new char[n][m];

        for (int i = 0; i < n; i++) {
            grid[i] = scanner.next().toCharArray();
        }

        Main main = new Main();
        Solution solution = main.new Solution();
        System.out.println(solution.numIslands(grid));
    }
}

C++ 代码

#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        if (grid.empty() || grid[0].empty()) return 0;
        int rows = grid.size(), cols = grid[0].size(), count = 0;

        for (int r = 0; r < rows; ++r) {
            for (int c = 0; c < cols; ++c) {
                if (grid[r][c] == '1') {
                    count++;
                    dfs(grid, r, c);
                }
            }
        }
        return count;
    }

private:
    void dfs(vector<vector<char>>& grid, int r, int c) {
        if (r < 0 || c < 0 || r >= grid.size() || c >= grid[0].size() || grid[r][c] == '0') {
            return;
        }

        grid[r][c] = '0'; // 标记访问
        dfs(grid, r + 1, c);
        dfs(grid, r - 1, c);
        dfs(grid, r, c + 1);
        dfs(grid, r, c - 1);
    }
};

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<char>> grid(n, vector<char>(m));

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> grid[i][j];
        }
    }

    Solution solution;
    cout << solution.numIslands(grid) << endl;
    return 0;
}

广度优先搜索（BFS）解法

Python 代码

from collections import deque

class Solution:
    def numIslands(self, grid):
        if not grid or not grid[0]:
            return 0
        
        rows, cols = len(grid), len(grid[0])
        count = 0
        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]  # 四个方向

        def bfs(r, c):
            queue = deque([(r, c)])
            grid[r][c] = '0'  # 标记已访问
            
            while queue:
                x, y = queue.popleft()
                for dx, dy in directions:
                    nx, ny = x + dx, y + dy
                    if 0 <= nx < rows and 0 <= ny < cols and grid[nx][ny] == '1':
                        queue.append((nx, ny))
                        grid[nx][ny] = '0'  # 标记已访问
        
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == '1':
                    count += 1
                    bfs(r, c)

        return count

# 读取输入
if __name__ == "__main__":
    n, m = map(int, input().split())
    grid = [list(input().strip()) for _ in range(n)]
    solution = Solution()
    print(solution.numIslands(grid))

Java 代码

import java.util.*;

public class Main {
    public class Solution {
        public int numIslands(char[][] grid) {
            if (grid == null || grid.length == 0) return 0;

            int rows = grid.length, cols = grid[0].length, count = 0;
            int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; // 四个方向

            for (int r = 0; r < rows; r++) {
                for (int c = 0; c < cols; c++) {
                    if (grid[r][c] == '1') {
                        count++;
                        bfs(grid, r, c, directions);
                    }
                }
            }
            return count;
        }

        private void bfs(char[][] grid, int r, int c, int[][] directions) {
            Queue<int[]> queue = new LinkedList<>();
            queue.offer(new int[]{r, c});
            grid[r][c] = '0'; // 标记已访问

            while (!queue.isEmpty()) {
                int[] cell = queue.poll();
                int x = cell[0], y = cell[1];

                for (int[] dir : directions) {
                    int nx = x + dir[0], ny = y + dir[1];
                    if (nx >= 0 && ny >= 0 && nx < grid.length && ny < grid[0].length && grid[nx][ny] == '1') {
                        queue.offer(new int[]{nx, ny});
                        grid[nx][ny] = '0'; // 标记已访问
                    }
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(), m = scanner.nextInt();
        char[][] grid = new char[n][m];

        for (int i = 0; i < n; i++) {
            grid[i] = scanner.next().toCharArray();
        }

        Main main = new Main();
        Solution solution = main.new Solution();
        System.out.println(solution.numIslands(grid));
    }
}

C++ 代码

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        if (grid.empty() || grid[0].empty()) return 0;

        int rows = grid.size(), cols = grid[0].size(), count = 0;
        vector<pair<int, int>> directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; // 四个方向

        for (int r = 0; r < rows; ++r) {
            for (int c = 0; c < cols; ++c) {
                if (grid[r][c] == '1') {
                    count++;
                    bfs(grid, r, c, directions);
                }
            }
        }
        return count;
    }

private:
    void bfs(vector<vector<char>>& grid, int r, int c, vector<pair<int, int>>& directions) {
        queue<pair<int, int>> q;
        q.push({r, c});
        grid[r][c] = '0'; // 标记已访问

        while (!q.empty()) {
            auto [x, y] = q.front();
            q.pop();

            for (auto [dx, dy] : directions) {
                int nx = x + dx, ny = y + dy;
                if (nx >= 0 && ny >= 0 && nx < grid.size() && ny < grid[0].size() && grid[nx][ny] == '1') {
                    q.push({nx, ny});
                    grid[nx][ny] = '0'; // 标记已访问
                }
            }
        }
    }
};

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<char>> grid(n, vector<char>(m));

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> grid[i][j];
        }
    }

    Solution solution;
    cout << solution.numIslands(grid) << endl;
    return 0;
}

题目内容

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

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

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

输入描述

• 第一行两个整数$n,m$，表示网格大小为$n×m$
• 接下来有$n$行，每行$m$列，表示网格。

输出描述

一个整数，表示网格中岛屿的数量

样例1

输入

4 5
11110
11010
11000
00000

输出

1

样例2

输入

4 5
11000
11000
00100
00011

输出

3

提示

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