第十一章：圖論part02

99. 島嶼數(shù)量 深搜

注意深搜的兩種寫法，熟練掌握這兩種寫法 以及 知道區(qū)別在哪里，才算掌握的深搜。
文章講解

思路

• 遇到一個(gè)沒有遍歷過的節(jié)點(diǎn)陸地，計(jì)數(shù)器就加一，然后把該節(jié)點(diǎn)陸地所能遍歷到的陸地都標(biāo)記上。

// 終止條件在調(diào)用dfs的地方
import java.util.Scanner;

class Main{
    // 定義四個(gè)方向的二維數(shù)組，表示上下左右四個(gè)方向的坐標(biāo)變化
    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];
        
        // 讀取網(wǎng)格數(shù)據(jù)
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                grid[i][j] = sc.nextInt();
            }
        }
        // 創(chuàng)建訪問標(biāo)記數(shù)組，初始化為false
        boolean[][] visited = new boolean[n][m];
        int result = 0;
        
        // 遍歷網(wǎng)格中的每一個(gè)元素
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                // 如果當(dāng)前元素是陸地且未訪問過
                if(!visited[i][j] && grid[i][j] == 1){
                    visited[i][j] = true; // 標(biāo)記為已訪問
                    result++;
                    dfs(grid, visited, i, j);
                }
            }
        }
        System.out.println(result);
    }
        
        private static void dfs(int[][] grid, boolean[][] visited, int x, int y){
            // 遍歷四個(gè)方向
            for(int i = 0; i < 4; i++){
                //計(jì)算下一個(gè)位置的x坐標(biāo)
                int nextx = x + dir[i][0];
                int nexty = y + dir[i][1];
                // 檢查是否越界
                // grid[0].length 表示二維數(shù)組中每一行的列數(shù)（即網(wǎng)格的寬度）。
                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; // 標(biāo)記為已訪問
                    dfs(grid, visited, nextx, nexty); // 遞歸調(diào)用，繼續(xù)搜索
                }
            }
            
        }
}

關(guān)于坐標(biāo)
int nextx = x + dir[i][0]; 這一行代碼的意思是計(jì)算下一個(gè)位置的 x 坐標(biāo)。為了更好地理解這個(gè)表達(dá)式，我們需要了解上下文和相關(guān)變量的定義。

在這個(gè)代碼中，dir 是一個(gè)二維數(shù)組，用于表示四個(gè)方向（上、右、下、左）的坐標(biāo)變化。具體定義如下：

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

• dir[0] 表示向右移動(dòng)，坐標(biāo)變化為 (0, 1)。
• dir[1] 表示向下移動(dòng)，坐標(biāo)變化為 (1, 0)。
• dir[2] 表示向上移動(dòng)，坐標(biāo)變化為 (-1, 0)。
• dir[3] 表示向左移動(dòng)，坐標(biāo)變化為 (0, -1)。

具體到數(shù)組元素：

dir[0] = {0, 1}：表示向右移動(dòng)

dir[0][0] = 0：x 坐標(biāo)不變
dir[0][1] = 1：y 坐標(biāo)增加 1
dir[1] = {1, 0}：表示向下移動(dòng)

dir[1][0] = 1：x 坐標(biāo)增加 1
dir[1][1] = 0：y 坐標(biāo)不變
dir[2] = {-1, 0}：表示向上移動(dòng)

dir[2][0] = -1：x 坐標(biāo)減少 1
dir[2][1] = 0：y 坐標(biāo)不變
dir[3] = {0, -1}：表示向左移動(dòng)

dir[3][0] = 0：x 坐標(biāo)不變
dir[3][1] = -1：y 坐標(biāo)減少 1

二維數(shù)組（如在圖像處理中）通常采用以下約定：

x 軸表示行（row），y 軸表示列（column）。
(0, 0) 表示左上角的元素。
x 坐標(biāo)增加表示向下移動(dòng)。
y 坐標(biāo)增加表示向右移動(dòng)。
為了進(jìn)一步解釋，我們來看看一個(gè)二維數(shù)組的表示方式：

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

在這個(gè)坐標(biāo)系統(tǒng)中：

向右移動(dòng)是 y 坐標(biāo)增加，即 (0, 0) -> (0, 1)。
向下移動(dòng)是 x 坐標(biāo)增加，即 (0, 0) -> (1, 0)。
向上移動(dòng)是 x 坐標(biāo)減少，即 (1, 0) -> (0, 0)。
向左移動(dòng)是 y 坐標(biāo)減少，即 (0, 1) -> (0, 0)。

圖示說明
假設(shè)我們有一個(gè)二維網(wǎng)格，起始點(diǎn)在 (x, y)：

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

向右移動(dòng)：(x, y) -> (x, y + 1)
向下移動(dòng)：(x, y) -> (x + 1, y)
向上移動(dòng)：(x, y) -> (x - 1, y)
向左移動(dòng)：(x, y) -> (x, y - 1)

// 終止條件放在開頭
import java.util.Scanner;

class Main {
    // 定義四個(gè)方向的二維數(shù)組，表示上下左右四個(gè)方向的坐標(biāo)變化
    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); // 創(chuàng)建Scanner對(duì)象用于輸入
        int n = scanner.nextInt(); // 讀取網(wǎng)格的行數(shù)
        int m = scanner.nextInt(); // 讀取網(wǎng)格的列數(shù)
        int[][] grid = new int[n][m]; // 創(chuàng)建網(wǎng)格并初始化

        // 讀取網(wǎng)格數(shù)據(jù)
        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]; // 創(chuàng)建訪問標(biāo)記數(shù)組，初始化為false
        int result = 0; // 結(jié)果變量，記錄島嶼數(shù)量

        // 遍歷網(wǎng)格中的每一個(gè)元素
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                // 如果當(dāng)前元素是陸地且未訪問過
                if (!visited[i][j] && grid[i][j] == 1) {
                    result++; // 發(fā)現(xiàn)一個(gè)新的島嶼，計(jì)數(shù)+1
                    dfs(grid, visited, i, j); // 深度優(yōu)先搜索，標(biāo)記所有相連的陸地
                }
            }
        }

        System.out.println(result); // 輸出結(jié)果，即島嶼數(shù)量
    }

    // 深度優(yōu)先搜索函數(shù)
    private static void dfs(int[][] grid, boolean[][] visited, int x, int y) {
        // 終止條件：訪問過的節(jié)點(diǎn) 或者 遇到海水
        if (visited[x][y] || grid[x][y] == 0) return;
        visited[x][y] = true; // 標(biāo)記訪問過

        // 遍歷四個(gè)方向
        for (int i = 0; i < 4; i++) {
            int nextx = x + dir[i][0]; // 計(jì)算下一個(gè)位置的x坐標(biāo)
            int nexty = y + dir[i][1]; // 計(jì)算下一個(gè)位置的y坐標(biāo)
            // 檢查是否越界
            if (nextx < 0 || nextx >= grid.length || nexty < 0 || nexty >= grid[0].length) continue;
            dfs(grid, visited, nextx, nexty); // 遞歸調(diào)用，繼續(xù)搜索
        }
    }
}

Java還是老老實(shí)實(shí)寫這個(gè)版本吧。。。

99. 島嶼數(shù)量 廣搜

注意廣搜的兩種寫法，第一種寫法為什么會(huì)超時(shí)。
文章講解

思路

• bfs要注意的點(diǎn)：超時(shí)根本原因是只要 加入隊(duì)列就代表 走過，就需要標(biāo)記，而不是從隊(duì)列拿出來的時(shí)候再去標(biāo)記走過。

// bfs

import java.util.*;

class Main {
    // 定義四個(gè)方向的二維數(shù)組，表示上下左右四個(gè)方向的坐標(biāo)變化
    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); // 創(chuàng)建Scanner對(duì)象用于輸入
        int n = scanner.nextInt(); // 讀取網(wǎng)格的行數(shù)
        int m = scanner.nextInt(); // 讀取網(wǎng)格的列數(shù)
        int[][] grid = new int[n][m]; // 創(chuàng)建網(wǎng)格并初始化

        // 讀取網(wǎng)格數(shù)據(jù)
        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]; // 創(chuàng)建訪問標(biāo)記數(shù)組，初始化為false
        int result = 0; // 結(jié)果變量，記錄島嶼數(shù)量

        // 遍歷網(wǎng)格中的每一個(gè)元素
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                // 如果當(dāng)前元素是陸地且未訪問過
                if (!visited[i][j] && grid[i][j] == 1) {
                    result++; // 發(fā)現(xiàn)一個(gè)新的島嶼，計(jì)數(shù)+1
                    bfs(grid, visited, i, j); // 深度優(yōu)先搜索，標(biāo)記所有相連的陸地
                }
            }
        }

        System.out.println(result); // 輸出結(jié)果，即島嶼數(shù)量
    }

    // 廣度優(yōu)先搜索函數(shù)
     private static void bfs(int[][] grid, boolean[][] visited, int x, int y) {
         Queue<int[]> queue = new LinkedList<>();
         queue.add(new int[]{x, y}); // 將起始點(diǎn)加入隊(duì)列
         visited[x][y] = true; // 只要加入隊(duì)列，立刻標(biāo)記為已訪問
         // 當(dāng)隊(duì)列不為空時(shí)，繼續(xù)搜索
         while(!queue.isEmpty()){
             int[] cur = queue.poll();
             int curx = cur[0];
             int cury = cur[1];
             
            //  遍歷四個(gè)方向
            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}); // 將新位置加入隊(duì)列
                    visited[nextx][nexty] = true; // 只要加入隊(duì)列，立刻標(biāo)記為已訪問
                }
            }
            
         }
         
     }
}

100. 島嶼的最大面積

本題就是基礎(chǔ)題了，做過上面的題目，本題很快。
文章講解

dfs的兩種寫法

版本一

在主函數(shù)中遇到島嶼時(shí)計(jì)數(shù)為1，dfs處理接下來的相鄰陸地：

import java.util.Scanner;

public class Main {
    static int count;
    static int[][] dir = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}}; // 四個(gè)方向

    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) { // 沒有訪問過的 同時(shí) 是陸地的
                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;  // 因?yàn)閐fs處理下一個(gè)節(jié)點(diǎn)，所以這里遇到陸地了就先計(jì)數(shù)，dfs處理接下來的相鄰陸地
                    visited[i][j] = true;
                    dfs(grid, visited, i, j); // 將與其鏈接的陸地都標(biāo)記上 true
                    result = Math.max(result, count);
                }
            }
        }
        System.out.println(result);
    }
}

版本二

在主函數(shù)中遇到島嶼時(shí)計(jì)數(shù)為0，dfs處理接下來的全部陸地：

import java.util.Scanner;

public class Main {
    static int count;
    static int[][] dir = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}}; // 四個(gè)方向

    public static void dfs(int[][] grid, boolean[][] visited, int x, int y) {
        if (visited[x][y] || grid[x][y] == 0) return; // 終止條件：訪問過的節(jié)點(diǎn) 或者 遇到海水
        visited[x][y] = true; // 標(biāo)記訪問過
        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; // 因?yàn)閐fs處理當(dāng)前節(jié)點(diǎn)，所以遇到陸地計(jì)數(shù)為0，進(jìn)dfs之后在開始從1計(jì)數(shù)
                    dfs(grid, visited, i, j); // 將與其鏈接的陸地都標(biāo)記上 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}}; // 四個(gè)方向

    // 廣度優(yōu)先搜索 (BFS) 方法，用于探索一個(gè)島嶼并統(tǒng)計(jì)其面積
    public static void bfs(int[][] grid, boolean[][] visited, int x, int y) {
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{x, y}); // 將初始坐標(biāo)加入隊(duì)列
        visited[x][y] = true; // 標(biāo)記初始坐標(biāo)已訪問
        count++; // 增加島嶼面積計(jì)數(shù)

        // 當(dāng)隊(duì)列不為空時(shí)，持續(xù)處理
        while (!queue.isEmpty()) {
            int[] current = queue.poll(); // 獲取并移除隊(duì)列頭部的元素
            int xx = current[0]; // 當(dāng)前處理的 x 坐標(biāo)
            int yy = current[1]; // 當(dāng)前處理的 y 坐標(biāo)
            // 遍歷四個(gè)方向
            for (int i = 0; i < 4; i++) {
                int nextx = xx + dir[i][0]; // 計(jì)算下一個(gè) x 坐標(biāo)
                int nexty = yy + dir[i][1]; // 計(jì)算下一個(gè) y 坐標(biāo)

                // 檢查下一個(gè)坐標(biāo)是否越界
                if (nextx < 0 || nextx >= grid.length || nexty < 0 || nexty >= grid[0].length) continue;

                // 如果下一個(gè)坐標(biāo)未被訪問且是陸地
                if (!visited[nextx][nexty] && grid[nextx][nexty] == 1) {
                    visited[nextx][nexty] = true; // 標(biāo)記為已訪問
                    count++; // 增加島嶼面積計(jì)數(shù)
                    queue.offer(new int[]{nextx, nexty}); // 將下一個(gè)坐標(biāo)加入隊(duì)列
                }
            }
        }
    }

    // 主方法，用于計(jì)算網(wǎng)格中島嶼的最大面積
    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);
    }
}

注意越界條件是大于等于