ID: 2226

Difficulty: 2

算法标签>

搜索

题目内容

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

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

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

输入描述

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

输出描述

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

样例1

输入

输出

样例2

输入

输出

提示

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

计算岛屿数量

题解思路

本题是一个典型的 连通区域个数 计算问题，可以用 深度优先搜索（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（深度优先搜索）	BFS（广度优先搜索）
搜索方式	递归或栈方式，优先深入一个方向到底	使用队列，逐层扩展相邻节点
代码实现	递归（或手动维护栈）实现较直观	需要使用队列维护搜索顺序
适用场景	适用于网格较小的情况，递归深度受限	适用于网格较大的情况，避免递归栈溢出
时间复杂度	`O(n×m)`，每个单元格访问一次
空间复杂度	`O(n×m)`（最坏情况下，递归深度可能达到网格大小）	`O(min(n, m))`（队列的最大深度一般不会超过某一维的长度）
优点	- 代码简单，递归方式直观 - 占用的内存通常较少（但递归栈可能较深）	- 适用于较大网格，避免递归栈溢出 - 可用于最短路径搜索（如迷宫问题）
缺点	- 可能导致递归栈溢出（特别是 `n×m` 较大时） - 在某些情况下比 BFS 慢	- 需要额外的队列存储空间 - 实现相对 DFS 复杂一些

深度优先搜索（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;
}

#P4019. 岛屿数量

岛屿数量

题目内容

输入描述

输出描述

样例1

样例2

提示

计算岛屿数量

题解思路

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

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

DFS与BFS

深度优先搜索（DFS）解法

广度优先搜索（BFS）解法

Status

Development

Support

#P4019. 岛屿数量 ⬅ 上一题 ➡ 下一题

岛屿数量

题目内容

输入描述

输出描述

样例1

样例2

提示

计算岛屿数量

题解思路

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

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

DFS与BFS

深度优先搜索（DFS）解法

广度优先搜索（BFS）解法

Status

Development

Support

#P4019. 岛屿数量