第十一章：图论part02

99. 岛屿数量 深搜

注意深搜的两种写法，熟练掌握这两种写法 以及 知道区别在哪里，才算掌握的深搜。
文章讲解

思路

• 遇到一个没有遍历过的节点陆地，计数器就加一，然后把该节点陆地所能遍历到的陆地都标记上。

// 终止条件在调用dfs的地方
import java.util.Scanner;

class Main{
    // 定义四个方向的二维数组，表示上下左右四个方向的坐标变化
    private static final int[][] dir = {{0,1},{1,0},{0,-1},{-1,0}};
    
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[][] grid = new int[n][m];
        
        // 读取网格数据
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                grid[i][j] = sc.nextInt();
            }
        }
        // 创建访问标记数组，初始化为false
        boolean[][] visited = new boolean[n][m];
        int result = 0;
        
        // 遍历网格中的每一个元素
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                // 如果当前元素是陆地且未访问过
                if(!visited[i][j] && grid[i][j] == 1){
                    visited[i][j] = true; // 标记为已访问
                    result++;
                    dfs(grid, visited, i, j);
                }
            }
        }
        System.out.println(result);
    }
        
        private static void dfs(int[][] grid, boolean[][] visited, int x, int y){
            // 遍历四个方向
            for(int i = 0; i < 4; i++){
                //计算下一个位置的x坐标
                int nextx = x + dir[i][0];
                int nexty = y + dir[i][1];
                // 检查是否越界
                // grid[0].length 表示二维数组中每一行的列数（即网格的宽度）。
                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(grid, visited, nextx, nexty); // 递归调用，继续搜索
                }
            }
            
        }
}

关于坐标
int nextx = x + dir[i][0]; 这一行代码的意思是计算下一个位置的 x 坐标。为了更好地理解这个表达式，我们需要了解上下文和相关变量的定义。

在这个代码中，dir 是一个二维数组，用于表示四个方向（上、右、下、左）的坐标变化。具体定义如下：

private static final int[][] dir = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}}; 

• dir[0] 表示向右移动，坐标变化为 (0, 1)。
• dir[1] 表示向下移动，坐标变化为 (1, 0)。
• dir[2] 表示向上移动，坐标变化为 (-1, 0)。
• dir[3] 表示向左移动，坐标变化为 (0, -1)。

具体到数组元素：

dir[0] = {0, 1}：表示向右移动

dir[0][0] = 0：x 坐标不变
dir[0][1] = 1：y 坐标增加 1
dir[1] = {1, 0}：表示向下移动

dir[1][0] = 1：x 坐标增加 1
dir[1][1] = 0：y 坐标不变
dir[2] = {-1, 0}：表示向上移动

dir[2][0] = -1：x 坐标减少 1
dir[2][1] = 0：y 坐标不变
dir[3] = {0, -1}：表示向左移动

dir[3][0] = 0：x 坐标不变
dir[3][1] = -1：y 坐标减少 1

二维数组（如在图像处理中）通常采用以下约定：

x 轴表示行（row），y 轴表示列（column）。
(0, 0) 表示左上角的元素。
x 坐标增加表示向下移动。
y 坐标增加表示向右移动。
为了进一步解释，我们来看看一个二维数组的表示方式：

(0,0)  (0,1)  (0,2)  ...
(1,0)  (1,1)  (1,2)  ...
(2,0)  (2,1)  (2,2)  ...

在这个坐标系统中：

向右移动是 y 坐标增加，即 (0, 0) -> (0, 1)。
向下移动是 x 坐标增加，即 (0, 0) -> (1, 0)。
向上移动是 x 坐标减少，即 (1, 0) -> (0, 0)。
向左移动是 y 坐标减少，即 (0, 1) -> (0, 0)。

图示说明
假设我们有一个二维网格，起始点在 (x, y)：

    y-1   y   y+1
x-1  .    .    .
 x   .  (x,y)  .
x+1  .    .    .

向右移动：(x, y) -> (x, y + 1)
向下移动：(x, y) -> (x + 1, y)
向上移动：(x, y) -> (x - 1, y)
向左移动：(x, y) -> (x, y - 1)

// 终止条件放在开头
import java.util.Scanner;

class Main {
    // 定义四个方向的二维数组，表示上下左右四个方向的坐标变化
    private static final int[][] dir = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}}; 

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in); // 创建Scanner对象用于输入
        int n = scanner.nextInt(); // 读取网格的行数
        int m = scanner.nextInt(); // 读取网格的列数
        int[][] grid = new int[n][m]; // 创建网格并初始化

        // 读取网格数据
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                grid[i][j] = scanner.nextInt();
            }
        }

        boolean[][] visited = new boolean[n][m]; // 创建访问标记数组，初始化为false
        int result = 0; // 结果变量，记录岛屿数量

        // 遍历网格中的每一个元素
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                // 如果当前元素是陆地且未访问过
                if (!visited[i][j] && grid[i][j] == 1) {
                    result++; // 发现一个新的岛屿，计数+1
                    dfs(grid, visited, i, j); // 深度优先搜索，标记所有相连的陆地
                }
            }
        }

        System.out.println(result); // 输出结果，即岛屿数量
    }

    // 深度优先搜索函数
    private static void dfs(int[][] grid, boolean[][] visited, int x, int y) {
        // 终止条件：访问过的节点 或者 遇到海水
        if (visited[x][y] || grid[x][y] == 0) return;
        visited[x][y] = true; // 标记访问过

        // 遍历四个方向
        for (int i = 0; i < 4; i++) {
            int nextx = x + dir[i][0]; // 计算下一个位置的x坐标
            int nexty = y + dir[i][1]; // 计算下一个位置的y坐标
            // 检查是否越界
            if (nextx < 0 || nextx >= grid.length || nexty < 0 || nexty >= grid[0].length) continue;
            dfs(grid, visited, nextx, nexty); // 递归调用，继续搜索
        }
    }
}

Java还是老老实实写这个版本吧。。。

99. 岛屿数量 广搜

注意广搜的两种写法，第一种写法为什么会超时。
文章讲解

思路

• bfs要注意的点：超时根本原因是只要 加入队列就代表 走过，就需要标记，而不是从队列拿出来的时候再去标记走过。

// bfs

import java.util.*;

class Main {
    // 定义四个方向的二维数组，表示上下左右四个方向的坐标变化
    private static final int[][] dir = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}}; 

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in); // 创建Scanner对象用于输入
        int n = scanner.nextInt(); // 读取网格的行数
        int m = scanner.nextInt(); // 读取网格的列数
        int[][] grid = new int[n][m]; // 创建网格并初始化

        // 读取网格数据
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                grid[i][j] = scanner.nextInt();
            }
        }

        boolean[][] visited = new boolean[n][m]; // 创建访问标记数组，初始化为false
        int result = 0; // 结果变量，记录岛屿数量

        // 遍历网格中的每一个元素
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                // 如果当前元素是陆地且未访问过
                if (!visited[i][j] && grid[i][j] == 1) {
                    result++; // 发现一个新的岛屿，计数+1
                    bfs(grid, visited, i, j); // 深度优先搜索，标记所有相连的陆地
                }
            }
        }

        System.out.println(result); // 输出结果，即岛屿数量
    }

    // 广度优先搜索函数
     private static void bfs(int[][] grid, boolean[][] visited, int x, int y) {
         Queue<int[]> queue = new LinkedList<>();
         queue.add(new int[]{x, y}); // 将起始点加入队列
         visited[x][y] = true; // 只要加入队列，立刻标记为已访问
         // 当队列不为空时，继续搜索
         while(!queue.isEmpty()){
             int[] cur = queue.poll();
             int curx = cur[0];
             int cury = cur[1];
             
            //  遍历四个方向
            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 int[]{nextx, nexty}); // 将新位置加入队列
                    visited[nextx][nexty] = true; // 只要加入队列，立刻标记为已访问
                }
            }
            
         }
         
     }
}

100. 岛屿的最大面积

本题就是基础题了，做过上面的题目，本题很快。
文章讲解

dfs的两种写法

版本一

在主函数中遇到岛屿时计数为1，dfs处理接下来的相邻陆地：

import java.util.Scanner;

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

    public static void dfs(int[][] grid, boolean[][] visited, int x, int y) {
        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;
                count++;
                dfs(grid, visited, nextx, nexty);
            }
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int[][] grid = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                grid[i][j] = scanner.nextInt();
            }
        }
        boolean[][] visited = new boolean[n][m];
        int result = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!visited[i][j] && grid[i][j] == 1) {
                    count = 1;  // 因为dfs处理下一个节点，所以这里遇到陆地了就先计数，dfs处理接下来的相邻陆地
                    visited[i][j] = true;
                    dfs(grid, visited, i, j); // 将与其链接的陆地都标记上 true
                    result = Math.max(result, count);
                }
            }
        }
        System.out.println(result);
    }
}

版本二

在主函数中遇到岛屿时计数为0，dfs处理接下来的全部陆地：

import java.util.Scanner;

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

    public static void dfs(int[][] grid, boolean[][] visited, int x, int y) {
        if (visited[x][y] || grid[x][y] == 0) return; // 终止条件：访问过的节点 或者 遇到海水
        visited[x][y] = true; // 标记访问过
        count++;
        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;  // 越界了，直接跳过
            dfs(grid, visited, nextx, nexty);
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int[][] grid = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                grid[i][j] = scanner.nextInt();
            }
        }
        boolean[][] visited = new boolean[n][m];
        int result = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!visited[i][j] && grid[i][j] == 1) {
                    count = 0; // 因为dfs处理当前节点，所以遇到陆地计数为0，进dfs之后在开始从1计数
                    dfs(grid, visited, i, j); // 将与其链接的陆地都标记上 true
                    result = Math.max(result, count);
                }
            }
        }
        System.out.println(result);
    }
}

bfs

import java.util.*;

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

    // 广度优先搜索 (BFS) 方法，用于探索一个岛屿并统计其面积
    public static void bfs(int[][] grid, boolean[][] visited, int x, int y) {
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{x, y}); // 将初始坐标加入队列
        visited[x][y] = true; // 标记初始坐标已访问
        count++; // 增加岛屿面积计数

        // 当队列不为空时，持续处理
        while (!queue.isEmpty()) {
            int[] current = queue.poll(); // 获取并移除队列头部的元素
            int xx = current[0]; // 当前处理的 x 坐标
            int yy = current[1]; // 当前处理的 y 坐标
            // 遍历四个方向
            for (int i = 0; i < 4; i++) {
                int nextx = xx + dir[i][0]; // 计算下一个 x 坐标
                int nexty = yy + dir[i][1]; // 计算下一个 y 坐标

                // 检查下一个坐标是否越界
                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; // 标记为已访问
                    count++; // 增加岛屿面积计数
                    queue.offer(new int[]{nextx, nexty}); // 将下一个坐标加入队列
                }
            }
        }
    }

    // 主方法，用于计算网格中岛屿的最大面积
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[][] grid = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                grid[i][j] = sc.nextInt();
            }
        }
        boolean[][] visited = new boolean[n][m];
        int result = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!visited[i][j] && grid[i][j] == 1) {
                    count = 0;
                    bfs(grid, visited, i, j);
                    result = Math.max(result, count);
                }
            }
        }
        System.out.println(result);
    }
}

注意越界条件是大于等于