代码随想录第五十一天| 99.岛屿数量深搜 99. 岛屿数量广搜 100.岛屿的最大面积-CSDN博客

本文链接：https://blog.csdn.net/Sweeping_Robot/article/details/146197431

岛屿数量问题

题目描述

给定一个由 1（陆地）和 0（水）组成的矩阵，计算岛屿的数量。岛屿由水平方向或垂直方向上相邻的陆地连接而成，并且四周都是水域。矩阵外均被水包围。

解题思路

深度优先搜索（DFS）

遍历整个矩阵，当遇到未访问过的陆地（值为1且未被标记为已访问）时，岛屿数量加1。
使用DFS标记与该陆地相连的所有陆地为已访问，避免重复计数。
通过方向数组定义上下左右四个方向，递归访问相邻陆地。

广度优先搜索（BFS）

同样遍历矩阵，遇到未访问的陆地时，岛屿数量加1。
使用队列存储待访问的陆地坐标，逐个出队并标记为已访问。
对于每个出队的陆地，检查其四个方向的相邻陆地，将符合条件的未访问陆地入队。

代码实现

DFS 实现

import java.util.Scanner;

public class Main {
    public static int[][] dir = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}}; // 定义四个方向

    public static void dfs(boolean[][] visited, int x, int y, int[][] grid) {
        for (int i = 0; i < 4; i++) {
            int nextX = x + dir[i][0];
            int nextY = y + dir[i][1];
            if (nextX < 0 || nextX >= grid.length || nextY < 0 || nextY >= grid[0].length) {
                continue; // 跳过越界情况
            }
            if (!visited[nextX][nextY] && grid[nextX][nextY] == 1) {
                visited[nextX][nextY] = true;
                dfs(visited, nextX, nextY, grid); // 递归访问相邻陆地
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int n = sc.nextInt();
        int[][] grid = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                grid[i][j] = sc.nextInt();
            }
        }
        boolean[][] visited = new boolean[m][n];
        int ans = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (!visited[i][j] && grid[i][j] == 1) {
                    ans++;
                    visited[i][j] = true;
                    dfs(visited, i, j, grid); // 深度优先搜索标记相连陆地
                }
            }
        }
        System.out.println(ans);
    }
}

BFS 实现

import java.util.*;

public class Main {
    public static int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};//下右上左逆时针遍历

    public static void bfs(int[][] grid, boolean[][] visited, int x, int y) {
        Queue<pair> queue = new LinkedList<pair>();//定义坐标队列，没有现成的pair类，在下面自定义了
        queue.add(new pair(x, y));
        visited[x][y] = true;//遇到入队直接标记为优先，
        // 否则出队时才标记的话会导致重复访问，比如下方节点会在右下顺序的时候被第二次访问入队
        while (!queue.isEmpty()) {
            int curX = queue.peek().first;
            int curY = queue.poll().second;//当前横纵坐标
            for (int i = 0; i < 4; i++) {
                //顺时针遍历新节点next，下面记录坐标
                int nextX = curX + dir[i][0];
                int nextY = curY + dir[i][1];
                if (nextX < 0 || nextX >= grid.length || nextY < 0 || nextY >= grid[0].length) {
                    continue;
                }//去除越界部分
                if (!visited[nextX][nextY] && grid[nextX][nextY] == 1) {
                    queue.add(new pair(nextX, nextY));
                    visited[nextX][nextY] = true;//逻辑同上
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int n = sc.nextInt();
        int[][] grid = new int[m][n];
        boolean[][] visited = new boolean[m][n];
        int ans = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                grid[i][j] = sc.nextInt();
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (!visited[i][j] && grid[i][j] == 1) {
                    ans++;
                    bfs(grid, visited, i, j);
                }
            }
        }
        System.out.println(ans);
    }
}

DFS与BFS在岛屿数量问题中的区别

搜索方式

DFS：在岛屿数量问题中，DFS会从一个未被访问的陆地出发，沿着一个方向（如向下、向右等）一直搜索，直到找不到新的陆地为止，然后回溯到上一个有未访问陆地的方向继续搜索，直到标记完所有与初始陆地相连的陆地。
BFS：从一个未被访问的陆地出发，先访问其上下左右四个方向的陆地，然后将这些陆地的上下左右方向的陆地加入队列，逐层扩展，直到所有相连的陆地都被标记为已访问。

实现方式

DFS：通常使用递归实现，代码较为简洁。在岛屿数量问题中，递归函数会处理当前陆地的四个方向，并对符合条件的陆地进行递归调用。
BFS：使用队列实现，需要显式地管理一个队列来存储待访问的陆地坐标。在岛屿数量问题中，每次从队列中取出一个陆地坐标，然后检查其四个方向的陆地，将符合条件的陆地加入队列并标记为已访问。

内存使用

DFS：在岛屿数量问题中，如果岛屿很大，递归深度可能会很大，可能导致栈溢出。例如，一个非常长的条形岛屿可能会使递归调用栈很深。
BFS：内存使用相对稳定，因为队列的大小取决于同一层的陆地数量。在岛屿数量问题中，最坏情况下队列中可能存储整个岛屿的所有陆地，但对于大多数情况，尤其是岛屿分布较分散时，内存使用较为可控。

时间复杂度

在岛屿数量问题中，无论是DFS还是BFS，时间复杂度都是O(m×n)，其中m和n是矩阵的行数和列数。这是因为每个陆地都需要被访问一次，且每个陆地的四个方向都需要被检查一次。

适用场景

DFS：在岛屿数量问题中，如果矩阵不是特别大，或者岛屿的形状不会导致递归深度过大，DFS是一个简单且有效的选择。它适合快速实现和理解。
BFS：如果矩阵较大，或者岛屿可能非常长且狭窄，BFS可能更安全，因为它不会受到递归栈深度的限制。此外，如果需要在搜索过程中处理某些层次信息（例如计算岛屿的层数），BFS也更方便。

代码实现差异

DFS代码特点

// DFS代码示例（岛屿数量问题）
public static void dfs(boolean[][] visited, int x, int y, int[][] grid) {
    for (int i = 0; i < 4; i++) {
        int nextX = x + dir[i][0];
        int nextY = y + dir[i][1];
        if (nextX < 0 || nextX >= grid.length || nextY < 0 || nextY >= grid[0].length) {
            continue;
        }
        if (!visited[nextX][nextY] && grid[nextX][nextY] == 1) {
            visited[nextX][nextY] = true;
            dfs(visited, nextX, nextY, grid);
        }
    }
}

使用递归直接在函数内部处理四个方向的搜索。
代码较为简洁，但递归调用可能带来栈溢出风险。

BFS代码特点

// BFS代码示例（岛屿数量问题）
public static void bfs(int[][] grid, boolean[][] visited, int x, int y) {
    Queue<pair> queue = new LinkedList<>();
    queue.add(new pair(x, y));
    visited[x][y] = true;
    while (!queue.isEmpty()) {
        int curX = queue.peek().first;
        int curY = queue.poll().second;
        for (int i = 0; i < 4; i++) {
            int nextX = curX + dir[i][0];
            int nextY = curY + dir[i][1];
            if (nextX < 0 || nextX >= grid.length || nextY < 0 || nextY >= grid[0].length) {
                continue;
            }
            if (!visited[nextX][nextY] && grid[nextX][nextY] == 1) {
                queue.add(new pair(nextX, nextY));
                visited[nextX][nextY] = true;
            }
        }
    }
}

使用队列显式管理待访问节点，逐层扩展。
代码稍显复杂，但避免了递归带来的栈溢出问题。

100.岛屿的最大面积问题