第十一章：圖論part04

110. 字符串接龍

經(jīng)過上面的練習(xí)，大家可能會(huì)感覺 廣搜不過如此，都刷出自信了，本題讓大家初步感受一下，廣搜難不在廣搜本身，而是如何應(yīng)用廣搜。
文章講解

思路

image.png

實(shí)際上就是求最短路徑的長(zhǎng)度

需要解決兩個(gè)問題

1. 圖中的點(diǎn)如何連在一起的

• 判斷點(diǎn)與點(diǎn)之間是否有連線，需要判斷是不是差一個(gè)字符，如果差一個(gè)字符，那就是有鏈接。

2. 起點(diǎn)和終點(diǎn)的最短路徑長(zhǎng)度

• 這里無向圖求最短路，廣搜最為合適，廣搜只要搜到了終點(diǎn)，那么一定是最短的路徑。因?yàn)閺V搜就是以起點(diǎn)中心向四周擴(kuò)散的搜索。
• 本題如果用深搜，會(huì)比較麻煩，要在到達(dá)終點(diǎn)的不同路徑中選則一條最短路。 而廣搜只要達(dá)到終點(diǎn)，一定是最短路。

注意

• 本題是一個(gè)無向圖，需要用標(biāo)記位，標(biāo)記著節(jié)點(diǎn)是否走過，否則就會(huì)死循環(huán)！
• 使用set來檢查字符串是否出現(xiàn)在字符串集合里更快一些

我這樣寫過不了不知道為什么

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();  // 輸入單詞列表的大小
        sc.nextLine();  // 清除緩沖區(qū)
        String[] strs = sc.nextLine().split(" ");  // 輸入起始單詞和結(jié)束單詞

        List<String> wordList = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            wordList.add(sc.next());  // 添加每一個(gè)單詞到列表中
        }

        int result = ladderLength(strs[0], strs[1], wordList);
        System.out.println(result);  // 輸出結(jié)果
    }

    public static int ladderLength(String beginStr, String endStr, List<String> strList) {
        // 將單詞列表轉(zhuǎn)換為一個(gè)Set以便快速查找
        Set<String> wordSet = new HashSet<>(strList);

        // 如果endStr不在字典中，直接返回0，因?yàn)闊o法轉(zhuǎn)換
        if (!wordSet.contains(endStr)) {
            return 0;
        }

        // 用于記錄每個(gè)單詞是否訪問過，以及它在轉(zhuǎn)換路徑中的長(zhǎng)度
        Map<String, Integer> pathMap = new HashMap<>();

        // 初始化隊(duì)列，用于BFS遍歷
        Queue<String> queue = new LinkedList<>();
        queue.offer(beginStr);  // 將起始單詞加入隊(duì)列
        pathMap.put(beginStr, 1);  // 設(shè)置起始單詞的路徑長(zhǎng)度為1

        // 開始BFS遍歷
        while (!queue.isEmpty()) {
            // 從隊(duì)列中取出一個(gè)單詞
            String currentWord = queue.poll();
            int currentPath = pathMap.get(currentWord);  // 當(dāng)前路徑長(zhǎng)度

            // 對(duì)單詞的每一個(gè)字符進(jìn)行替換嘗試
            for (int i = 0; i < currentWord.length(); i++) {
                char[] wordArray = currentWord.toCharArray();  // 將字符串轉(zhuǎn)換為字符數(shù)組

                // 嘗試將每個(gè)字符替換為'a'到'z'中的任意一個(gè)字母
                for (char c = 'a'; c <= 'z'; c++) {
                    wordArray[i] = c;  // 替換字符
                    String newWord = new String(wordArray);  // 生成新單詞

                    // 如果新單詞就是目標(biāo)單詞，返回路徑長(zhǎng)度
                    if (newWord.equals(endStr)) {
                        return currentPath + 1;
                    }

                    // 如果新單詞在字典中，且之前未被訪問過
                    if (wordSet.contains(newWord) && !pathMap.containsKey(newWord)) {
                        pathMap.put(newWord, currentPath + 1);  // 記錄新單詞的路徑長(zhǎng)度
                        queue.offer(newWord);  // 將新單詞加入隊(duì)列
                    }
                }
            }
        }

        // 如果沒有找到目標(biāo)單詞，返回0
        return 0;
    }
}

這個(gè)能過

import java.util.*;

public class Main {
    // 全局變量用于存儲(chǔ)單詞集合和路徑信息
    static Set<String> wordSet = new HashSet<>();
    static Map<String, Integer> pathMap = new HashMap<>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();  // 輸入單詞列表的大小
        String beginStr = sc.next();  // 起始單詞
        String endStr = sc.next();  // 目標(biāo)單詞
        sc.nextLine();  // 清除緩沖區(qū)

        // 將所有單詞添加到wordSet中
        for (int i = 0; i < n; i++) {
            wordSet.add(sc.next());
        }

        // 初始節(jié)點(diǎn)的路徑長(zhǎng)度設(shè)置為1
        pathMap.put(beginStr, 1);

        // 使用隊(duì)列進(jìn)行廣度優(yōu)先搜索
        Queue<String> queue = new LinkedList<>();
        queue.offer(beginStr);  // 將起始單詞加入隊(duì)列

        // 開始BFS遍歷
        while (!queue.isEmpty()) {
            String currentWord = queue.poll();  // 取出當(dāng)前單詞
            int currentPath = pathMap.get(currentWord);  // 當(dāng)前路徑長(zhǎng)度

            // 對(duì)單詞的每一個(gè)字符進(jìn)行替換嘗試
            for (int i = 0; i < currentWord.length(); i++) {
                char[] wordArray = currentWord.toCharArray();  // 將字符串轉(zhuǎn)換為字符數(shù)組

                // 嘗試將每個(gè)字符替換為'a'到'z'中的任意一個(gè)字母
                for (char c = 'a'; c <= 'z'; c++) {
                    wordArray[i] = c;  // 替換字符
                    String newWord = new String(wordArray);  // 生成新單詞

                    // 如果新單詞就是目標(biāo)單詞，返回路徑長(zhǎng)度
                    if (newWord.equals(endStr)) {
                        System.out.println(currentPath + 1);
                        return;
                    }

                    // 如果新單詞在字典中，且之前未被訪問過
                    if (wordSet.contains(newWord) && !pathMap.containsKey(newWord)) {
                        pathMap.put(newWord, currentPath + 1);  // 記錄新單詞的路徑長(zhǎng)度
                        queue.offer(newWord);  // 將新單詞加入隊(duì)列
                    }
                }
            }
        }

        // 如果沒有找到目標(biāo)單詞，返回0
        System.out.println(0);
    }
}

之后要放到編譯器里調(diào)試一下

105. 有向圖的完全可達(dá)性

深搜有細(xì)節(jié)，同樣是深搜兩種寫法的區(qū)別，以及什么時(shí)候需要回溯操作呢？
文章講解

思路

本題是一個(gè)有向圖搜索全路徑的問題。 只能用深搜（DFS）或者廣搜（BFS）來搜。

深搜三部曲

1. 確認(rèn)遞歸函數(shù)，參數(shù)

• 需要傳入地圖，需要知道當(dāng)前我們拿到的key，以至于去下一個(gè)房間。
• 同時(shí)還需要一個(gè)數(shù)組，用來記錄我們都走過了哪些房間，這樣好知道最后有沒有把所有房間都遍歷的，可以定義一個(gè)一維數(shù)組。
  所以 遞歸函數(shù)參數(shù)如下：

// key 當(dāng)前得到的key 
// visited 記錄訪問過的房間 
void dfs(List<List<Integer>> graph, int key, boolean[] visited) {
    // 具體邏輯在下面實(shí)現(xiàn)
}

2. 確認(rèn)終止條件

• 遍歷的時(shí)候什么時(shí)候中止，要想清楚遞歸的時(shí)候是處理當(dāng)前訪問的節(jié)點(diǎn)，還是處理下一個(gè)要訪問的節(jié)點(diǎn)。
• 首先明確，本題中“處理” = 用 visited數(shù)組來記錄訪問過的節(jié)點(diǎn)，該節(jié)點(diǎn)默認(rèn) 數(shù)組里元素都是false，把元素標(biāo)記為true就是處理 本節(jié)點(diǎn)了。
• 如果我們是處理當(dāng)前訪問的節(jié)點(diǎn)，當(dāng)前訪問的節(jié)點(diǎn)如果是 true ，說明是訪問過的節(jié)點(diǎn)，那就終止本層遞歸，如果不是true，我們就把它賦值為true，因?yàn)檫@是我們處理本層遞歸的節(jié)點(diǎn)。

if (visited[key]) {
        return;
    }
    visited[key] = true;
    List<Integer> keys = graph.get(key);
    for (int nextKey : keys) {
        // 深度優(yōu)先搜索遍歷
        dfs(graph, nextKey, visited);
    }

寫法二：處理下一個(gè)要訪問的節(jié)點(diǎn)

void dfs(List<List<Integer>> graph, int key, boolean[] visited) {
    List<Integer> keys = graph.get(key);
    for (int nextKey : keys) {
        if (!visited[nextKey]) { // 確認(rèn)下一個(gè)是沒訪問過的節(jié)點(diǎn)
            visited[nextKey] = true;
            dfs(graph, nextKey, visited);
        }
    }
}

3. 處理目前搜索節(jié)點(diǎn)出發(fā)的路徑

• 上面終止條件有兩種不同的寫法，所以遞歸也有兩種寫法
• 為什么本題就沒有回溯呢？只有在需要搜索一條可行路徑的時(shí)候，就需要回溯操作了，因?yàn)闆]有回溯，就沒法“調(diào)頭”。本題只是求節(jié)點(diǎn)1能否到所有節(jié)點(diǎn)，就不必回溯，只要遍歷過的節(jié)點(diǎn)都一律標(biāo)記上。

寫法一：DFS 處理當(dāng)前訪問的節(jié)點(diǎn)

import java.util.*;

public class Main{
    // 寫法一：DFS 處理當(dāng)前訪問的節(jié)點(diǎn)
    public static void dfs(List<List<Integer>> graph, int key, boolean[] visited){
        if(visited[key]) return;
        visited[key] = true;
        List<Integer> keys = graph.get(key);
        for(int nextKey : keys){
            dfs(graph, nextKey, visited);
        }
        
    }
    
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt(); 
        int K = sc.nextInt();
        List<List<Integer>> graph = new ArrayList<>(N + 1);
        for(int i = 0; i <= N; i++){
            graph.add(new ArrayList<>());
        }
        for(int i = 0; i < K; i++){
            int s = sc.nextInt();
            int t = sc.nextInt();
            graph.get(s).add(t);
        }
        boolean[] visited = new boolean[N + 1];
        dfs(graph, 1, visited);
        // 檢查是否都訪問到了  節(jié)點(diǎn)編號(hào)從1開始
        for(int i = 1; i <= N; i++){
            if(!visited[i]){
                System.out.println(-1);
                return;
            }
        }
        System.out.println(1);
    }
}

寫法二：DFS 處理下一個(gè)要訪問的節(jié)點(diǎn)

import java.util.*;

public class Main {

    // DFS方法：處理下一個(gè)要訪問的節(jié)點(diǎn)
    public static void dfs(List<List<Integer>> graph, int key, boolean[] visited) {
        List<Integer> keys = graph.get(key);
        for (int nextKey : keys) {
            if (!visited[nextKey]) {  // 確認(rèn)下一個(gè)是沒訪問過的節(jié)點(diǎn)
                visited[nextKey] = true;
                dfs(graph, nextKey, visited);
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();  // 節(jié)點(diǎn)數(shù)
        int m = sc.nextInt();  // 邊數(shù)

        List<List<Integer>> graph = new ArrayList<>(n + 1);
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }

        for (int i = 0; i < m; i++) {
            int s = sc.nextInt();
            int t = sc.nextInt();
            graph.get(s).add(t);
        }

        boolean[] visited = new boolean[n + 1];
        visited[1] = true;  // 節(jié)點(diǎn)1 預(yù)先處理
        dfs(graph, 1, visited);

        // 檢查是否都訪問到了
        for (int i = 1; i <= n; i++) {
            if (!visited[i]) {
                System.out.println(-1);
                return;
            }
        }
        System.out.println(1);
    }
}

106. 島嶼的周長(zhǎng)

簡(jiǎn)單題，避免大家慣性思維，建議大家先獨(dú)立做題。
文章講解

思路

解法一

遍歷每一個(gè)空格，遇到島嶼（即值為 1）時(shí)，計(jì)算其上下左右四個(gè)方向的情況。如果在這些方向上有水域（即值為 0），或者超出了網(wǎng)格的邊界，則認(rèn)為這是島嶼的一條邊，并增加邊的計(jì)數(shù)。

image.png

import java.util.Scanner;

public class Main {
    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];
        
        // 輸入網(wǎng)格
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                grid[i][j] = scanner.nextInt();
            }
        }
        
        int[][] direction = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
        int result = 0;
        
        // 遍歷每一個(gè)空格
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 1) {  // 找到島嶼
                    for (int k = 0; k < 4; k++) {  // 計(jì)算四個(gè)方向
                        int x = i + direction[k][0];
                        int y = j + direction[k][1];
                        
                        // 判斷邊界和水域
                        if (x < 0 || x >= n || y < 0 || y >= m || grid[x][y] == 0) {
                            result++;
                        }
                    }
                }
            }
        }
        
        System.out.println(result);
    }
}

解法二

首先，計(jì)算出總的島嶼數(shù)量，然后假設(shè)每個(gè)島嶼的初始邊數(shù)是 4，即總邊數(shù)為 島嶼數(shù)量 * 4。然后，計(jì)算相鄰島嶼的數(shù)量，因?yàn)槊繉?duì)相鄰的島嶼共用一條邊，因此每對(duì)相鄰的島嶼會(huì)減少 2 條邊。

image.png

import java.util.Scanner;

public class Main {
    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];
        
        // 輸入網(wǎng)格
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                grid[i][j] = scanner.nextInt();
            }
        }
        
        int sum = 0; // 陸地?cái)?shù)量
        int cover = 0; // 相鄰數(shù)量
        // 遍歷每一個(gè)空格
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(grid[i][j] == 1){
                    sum++;
                    // 統(tǒng)計(jì)上邊相鄰陸地
                    if(i - 1 >= 0 && grid[i - 1][j] == 1) cover++;
                    // 統(tǒng)計(jì)下邊相鄰陸地
                    if(j - 1 >= 0 && grid[i][j - 1] == 1) cover++;
                }
                
            }
        }
        int result = sum * 4 - cover * 2;
        System.out.println(result);
    }
}