第十一章：圖論part04
110. 字符串接龍
經(jīng)過(guò)上面的練習(xí)咳蔚，大家可能會(huì)感覺(jué) 廣搜不過(guò)如此，都刷出自信了搔驼，本題讓大家初步感受一下谈火，廣搜難不在廣搜本身，而是如何應(yīng)用廣搜舌涨。
文章講解
思路
image.png
實(shí)際上就是求最短路徑的長(zhǎng)度
需要解決兩個(gè)問(wèn)題
- 圖中的點(diǎn)如何連在一起的
- 判斷點(diǎn)與點(diǎn)之間是否有連線糯耍，需要判斷是不是差一個(gè)字符，如果差一個(gè)字符囊嘉，那就是有鏈接谍肤。
- 起點(diǎn)和終點(diǎn)的最短路徑長(zhǎng)度
- 這里無(wú)向圖求最短路，廣搜最為合適哗伯，廣搜只要搜到了終點(diǎn)，那么一定是最短的路徑篷角。因?yàn)閺V搜就是以起點(diǎn)中心向四周擴(kuò)散的搜索焊刹。
- 本題如果用深搜，會(huì)比較麻煩恳蹲，要在到達(dá)終點(diǎn)的不同路徑中選則一條最短路虐块。 而廣搜只要達(dá)到終點(diǎn)，一定是最短路嘉蕾。
注意
- 本題是一個(gè)無(wú)向圖贺奠，需要用標(biāo)記位，標(biāo)記著節(jié)點(diǎn)是否走過(guò)错忱，否則就會(huì)死循環(huán)儡率！
- 使用set來(lái)檢查字符串是否出現(xiàn)在字符串集合里更快一些
我這樣寫過(guò)不了不知道為什么
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(wú)法轉(zhuǎn)換
if (!wordSet.contains(endStr)) {
return 0;
}
// 用于記錄每個(gè)單詞是否訪問(wèn)過(guò)儿普，以及它在轉(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
// 開(kāi)始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;
}
// 如果新單詞在字典中眉孩，且之前未被訪問(wèn)過(guò)
if (wordSet.contains(newWord) && !pathMap.containsKey(newWord)) {
pathMap.put(newWord, currentPath + 1); // 記錄新單詞的路徑長(zhǎng)度
queue.offer(newWord); // 將新單詞加入隊(duì)列
}
}
}
}
// 如果沒(méi)有找到目標(biāo)單詞，返回0
return 0;
}
}
這個(gè)能過(guò)
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ì)列
// 開(kāi)始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;
}
// 如果新單詞在字典中浪汪，且之前未被訪問(wèn)過(guò)
if (wordSet.contains(newWord) && !pathMap.containsKey(newWord)) {
pathMap.put(newWord, currentPath + 1); // 記錄新單詞的路徑長(zhǎng)度
queue.offer(newWord); // 將新單詞加入隊(duì)列
}
}
}
}
// 如果沒(méi)有找到目標(biāo)單詞，返回0
System.out.println(0);
}
}
之后要放到編譯器里調(diào)試一下
105. 有向圖的完全可達(dá)性
深搜有細(xì)節(jié)凛虽，同樣是深搜兩種寫法的區(qū)別死遭，以及什么時(shí)候需要回溯操作呢？
文章講解
思路
本題是一個(gè)有向圖搜索全路徑的問(wèn)題。 只能用深搜（DFS）或者廣搜（BFS）來(lái)搜怜浅。
深搜三部曲
1. 確認(rèn)遞歸函數(shù)，參數(shù)
- 需要傳入地圖披泪，需要知道當(dāng)前我們拿到的key蜗侈，以至于去下一個(gè)房間篷牌。
- 同時(shí)還需要一個(gè)數(shù)組，用來(lái)記錄我們都走過(guò)了哪些房間踏幻，這樣好知道最后有沒(méi)有把所有房間都遍歷的枷颊，可以定義一個(gè)一維數(shù)組。
所以 遞歸函數(shù)參數(shù)如下：
// key 當(dāng)前得到的key
// visited 記錄訪問(wèn)過(guò)的房間
void dfs(List<List<Integer>> graph, int key, boolean[] visited) {
// 具體邏輯在下面實(shí)現(xiàn)
}
2. 確認(rèn)終止條件
- 遍歷的時(shí)候什么時(shí)候中止该面，要想清楚遞歸的時(shí)候是處理當(dāng)前訪問(wèn)的節(jié)點(diǎn)夭苗，還是處理下一個(gè)要訪問(wèn)的節(jié)點(diǎn)。
- 首先明確隔缀，本題中“處理” = 用 visited數(shù)組來(lái)記錄訪問(wèn)過(guò)的節(jié)點(diǎn)题造，該節(jié)點(diǎn)默認(rèn) 數(shù)組里元素都是false，把元素標(biāo)記為true就是處理 本節(jié)點(diǎn)了猾瘸。
- 如果我們是處理當(dāng)前訪問(wèn)的節(jié)點(diǎn)界赔，當(dāng)前訪問(wèn)的節(jié)點(diǎn)如果是 true ，說(shuō)明是訪問(wèn)過(guò)的節(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è)要訪問(wèn)的節(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è)是沒(méi)訪問(wèn)過(guò)的節(jié)點(diǎn)
visited[nextKey] = true;
dfs(graph, nextKey, visited);
}
}
}
3. 處理目前搜索節(jié)點(diǎn)出發(fā)的路徑
- 上面終止條件有兩種不同的寫法，所以遞歸也有兩種寫法
- 為什么本題就沒(méi)有回溯呢钉汗？只有在需要搜索一條可行路徑的時(shí)候羹令，就需要回溯操作了，因?yàn)闆](méi)有回溯儡湾，就沒(méi)法“調(diào)頭”特恬。本題只是求節(jié)點(diǎn)1能否到所有節(jié)點(diǎn)，就不必回溯徐钠，只要遍歷過(guò)的節(jié)點(diǎn)都一律標(biāo)記上癌刽。
寫法一：DFS 處理當(dāng)前訪問(wèn)的節(jié)點(diǎn)
import java.util.*;
public class Main{
// 寫法一：DFS 處理當(dāng)前訪問(wèn)的節(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);
// 檢查是否都訪問(wèn)到了 節(jié)點(diǎn)編號(hào)從1開(kāi)始
for(int i = 1; i <= N; i++){
if(!visited[i]){
System.out.println(-1);
return;
}
}
System.out.println(1);
}
}
寫法二：DFS 處理下一個(gè)要訪問(wèn)的節(jié)點(diǎn)
import java.util.*;
public class Main {
// DFS方法：處理下一個(gè)要訪問(wèn)的節(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è)是沒(méi)訪問(wèn)過(guò)的節(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);
// 檢查是否都訪問(wèn)到了
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);
}
}
