圖論匯總1

1.圖論理論基礎

圖的基本概念

二維坐標中，兩點可以連成線，多個點連成的線就構成了圖。

當然圖也可以就一個節點，甚至沒有節點（空圖）

圖的種類

整體上一般分為有向圖和無向圖。

有向圖是指圖中邊是有方向的：

無向圖是指圖中邊沒有方向：

加權有向圖，就是圖中邊是有權值的，例如：

加權無向圖也是同理。

度

無向圖中有幾條邊連接該節點，該節點就有幾度。

例如，該無向圖中，節點4的度為5，節點6的度為3。

在有向圖中，每個節點有出度和入度。

出度：從該節點出發的邊的個數。

入度：指向該節點邊的個數。

例如，該有向圖中，節點3的入度為2，出度為1，節點1的入度為0，出度為2。

連通性

在圖中表示節點的連通情況，我們稱之為連通性。

連通圖

在無向圖中，任何兩個節點都是可以到達的，我們稱之為連通圖，如圖：

如果有節點不能到達其他節點，則為非連通圖，如圖：

節點1 不能到達節點4。

強連通圖

在有向圖中，任何兩個節點是可以相互到達的，我們稱之為強連通圖。

這里有錄友可能想，這和無向圖中的連通圖有什么區別，不是一樣的嗎？

我們來看這個有向圖：

這個圖是強連通圖嗎？

初步一看，好像這節點都連著呢，但這不是強連通圖，節點1 可以到節點5，但節點5 不能到節點1 。

強連通圖是在有向圖中任何兩個節點是可以相互到達

下面這個有向圖才是強連通圖：

連通分量

在無向圖中的極大連通子圖稱之為該圖的一個連通分量。

只看概念大家可能不理解，我來畫個圖：

該無向圖中節點1、節點2、節點5 構成的子圖就是該無向圖中的一個連通分量，該子圖所有節點都是相互可達到的。

同理，節點3、節點4、節點6 構成的子圖也是該無向圖中的一個連通分量。

那么無向圖中節點3 、節點4 構成的子圖是該無向圖的聯通分量嗎？

不是！

因為必須是極大聯通子圖才能是連通分量，所以必須是節點3、節點4、節點6 構成的子圖才是連通分量。

在圖論中，連通分量是一個很重要的概念，例如島嶼問題（后面章節會有專門講解）其實就是求連通分量。

強連通分量

在有向圖中極大強連通子圖稱之為該圖的強連通分量。

如圖：

節點1、節點2、節點3、節點4、節點5 構成的子圖是強連通分量，因為這是強連通圖，也是極大圖。

節點6、節點7、節點8 構成的子圖不是強連通分量，因為這不是強連通圖，節點8 不能達到節點6。

節點1、節點2、節點5 構成的子圖也不是強連通分量，因為這不是極大圖。

圖的構造

我們如何用代碼來表示一個圖呢？

一般使用鄰接表、鄰接矩陣或者用類來表示。

主要是樸素存儲、鄰接表和鄰接矩陣。

鄰接矩陣

鄰接矩陣使用二維數組來表示圖結構。鄰接矩陣是從節點的角度來表示圖，有多少節點就申請多大的二維數組。

例如： grid[2][5] = 6，表示節點 2 連接節點5 為有向圖，節點2 指向節點5，邊的權值為6。

如果想表示無向圖，即：grid[2][5] = 6，grid[5][2] = 6，表示節點2 與節點5 相互連通，權值為6。

如圖：

在一個 n （節點數）為8 的圖中，就需要申請 8 * 8 這么大的空間。

圖中有一條雙向邊，即：grid[2][5] = 6，grid[5][2] = 6

這種表達方式（鄰接矩陣）在邊少，節點多的情況下，會導致申請過大的二維數組，造成空間浪費。

而且在尋找節點連接情況的時候，需要遍歷整個矩陣，即 n * n 的時間復雜度，同樣造成時間浪費。

鄰接矩陣的優點：

表達方式簡單，易于理解
檢查任意兩個頂點間是否存在邊的操作非常快
適合稠密圖，在邊數接近頂點數平方的圖中，鄰接矩陣是一種空間效率較高的表示方法。

缺點：

遇到稀疏圖，會導致申請過大的二維數組造成空間浪費且遍歷邊的時候需要遍歷整個n * n矩陣，造成時間浪費。

鄰接表

鄰接表使用數組 + 鏈表的方式來表示。鄰接表是從邊的數量來表示圖，有多少邊才會申請對應大小的鏈表。

鄰接表的構造如圖：

這里表達的圖是：

節點1 指向節點3 和節點5
節點2 指向節點4、節點3、節點5
節點3 指向節點4
節點4指向節點1

有多少邊鄰接表才會申請多少個對應的鏈表節點。

從圖中可以直觀看出使用數組 + 鏈表來表達邊的連接情況。

鄰接表的優點：

對于稀疏圖的存儲，只需要存儲邊，空間利用率高
遍歷節點連接情況相對容易

缺點：

檢查任意兩個節點間是否存在邊，效率相對低，需要 O(V)時間，V表示某節點連接其他節點的數量。
實現相對復雜，不易理解

圖的遍歷方式

圖的遍歷方式基本是兩大類：

深度優先搜索（dfs）
廣度優先搜索（bfs）

二叉樹的遞歸遍歷，是dfs 在二叉樹上的遍歷方式。

二叉樹的層序遍歷，是bfs 在二叉樹上的遍歷方式。

dfs 和 bfs 一種搜索算法，可以在不同的數據結構上進行搜索，在二叉樹章節里是在二叉樹這樣的數據結構上搜索。

而在圖論章節，則是在圖（鄰接表或鄰接矩陣）上進行搜索。

2.深度優先搜索理論基礎

dfs 與 bfs 區別

深度優先搜索（dfs）和廣度優先搜索（bfs）區別

dfs是可一個方向去搜，不到黃河不回頭，直到遇到絕境了，搜不下去了，再換方向（換方向的過程就涉及到了回溯）。
bfs是先把本節點所連接的所有節點遍歷一遍，走到下一個節點的時候，再把連接節點的所有節點遍歷一遍，搜索方向更像是廣度，四面八方的搜索過程。

dfs 搜索過程

圖一是一個無向圖，我們要搜索從節點1到節點6的所有路徑。

那么dfs搜索的第一條路徑是這樣的：（假設第一次延默認方向，就找到了節點6），圖二

此時我們找到了節點6，（遇到黃河了，是不是應該回頭了），那么應該再去搜索其他方向了。如圖三：

路徑2撤銷了，改變了方向，走路徑3（紅色線），接著也找到終點6。那么撤銷路徑2，改為路徑3，在dfs中其實就是回溯的過程。

又找到了一條從節點1到節點6的路徑，又到黃河了，此時再回頭，下圖圖四中，路徑4撤銷（回溯的過程），改為路徑5。

又找到了一條從節點1到節點6的路徑，又到黃河了，此時再回頭，下圖圖五，路徑6撤銷（回溯的過程），改為路徑7，路徑8 和路徑7，路徑9，結果發現死路一條，都走到了自己走過的節點。

那么節點2所連接路徑和節點3所鏈接的路徑都走過了，撤銷路徑只能向上回退，去選擇撤銷當初節點4的選擇，也就是撤銷路徑5，改為路徑10 。如圖圖六：

上圖演示中，其實我并沒有把所有的從節點1 到節點6的dfs（深度優先搜索）的過程都畫出來，那樣太冗余了，但已經把dfs 關鍵的地方都涉及到了，關鍵就兩點：

搜索方向，是認準一個方向搜，直到碰壁之后再換方向
換方向是撤銷原路徑，改為節點鏈接的下一個路徑，回溯的過程。

深搜三部曲

在?二叉樹遞歸講解中，給出了遞歸三部曲。

回溯算法講解中，給出了回溯三部曲。

其實深搜也是一樣的，深搜三部曲如下：

確認遞歸函數，參數
確認終止條件
處理目前搜索節點出發的路徑

3.所有可達路徑

卡碼網題目鏈接（ACM模式）(opens new window)

【題目描述】

給定一個有 n 個節點的有向無環圖，節點編號從 1 到 n。請編寫一個函數，找出并返回所有從節點 1 到節點 n 的路徑。每條路徑應以節點編號的列表形式表示。

【輸入描述】

第一行包含兩個整數 N，M，表示圖中擁有 N 個節點，M 條邊

后續 M 行，每行包含兩個整數 s 和 t，表示圖中的 s 節點與 t 節點中有一條路徑

【輸出描述】

輸出所有的可達路徑，路徑中所有節點的后面跟一個空格，每條路徑獨占一行，存在多條路徑，路徑輸出的順序可任意。

如果不存在任何一條路徑，則輸出 -1。

注意輸出的序列中，最后一個節點后面沒有空格！例如正確的答案是?1 3 5,而不是?1 3 5， 5后面沒有空格！

【輸入示例】

【輸出示例】

1 3 5
1 2 4 5

提示信息

用例解釋：

有五個節點，其中的從 1 到達 5 的路徑有兩個，分別是 1 -> 3 -> 5 和 1 -> 2 -> 4 -> 5。

因為擁有多條路徑，所以輸出結果為：

1 3 5
1 2 4 5

或

1 2 4 5
1 3 5

都算正確。

數據范圍：

圖中不存在自環
圖中不存在平行邊
1 <= N <= 100
1 <= M <= 500

采用深度優先搜索（DFS）算法來遍歷圖，找出從節點 1 到節點?n?的所有路徑。具體步驟如下：

讀取圖的節點數和邊數，并構建圖的鄰接矩陣。
從節點 1 開始進行深度優先搜索，在搜索過程中記錄當前路徑。
當到達目標節點?n?時，將當前路徑添加到結果列表中。
最后輸出所有找到的路徑，如果沒有找到任何路徑，則輸出 -1。

在無向圖的鄰接矩陣表示里，通常會創建一個?n x n?的二維數組?graph，這里的?n?是圖中節點的數量。數組的行和列分別對應圖中的節點，graph[i][j]?表示節點?i?到節點?j?是否存在邊。當?graph[i][j] = 1?時，意味著節點?i?和節點?j?之間存在一條直接相連的邊；若?graph[i][j] = 0，則表示這兩個節點之間沒有直接相連的邊。

對于無向圖而言，由于邊是無方向的，即如果節點?i?到節點?j?有邊，那么節點?j?到節點?i?也必然有邊，所以鄰接矩陣是對稱的，也就是?graph[i][j]?始終等于?graph[j][i]。

public class All_Reachable_Paths {static List<List<Integer>> result = new ArrayList<>();//維列表，用于存儲所有從節點 1 到節點 n 的路徑。每個路徑是一個整數列表，而 result 列表包含所有這樣的路徑列表。static List<Integer> path = new ArrayList<>();//維列表，用于在深度優先搜索（DFS）過程中存儲當前正在探索的路徑。public static void dfs(int[][] graph, int x, int n) {//遞歸方法，用于執行深度優先搜索。int[][] graph 參數代表圖的鄰接矩陣，其中graph[i][j] = 1表示節點i和節點j之間有一條邊。int x 是當前節點。int n 是目標節點。if (x == n) {//當當前節點 x 等于目標節點 n 時，說明找到了一條從節點 1 到節點 n 的路徑。將當前路徑 path 的副本添加到結果列表 result 中，然后返回。result.add(new ArrayList<>(path));return;}//對于圖中的每個節點i（從1到n），檢查是否存在從當前節點x到節點i的邊（graph[x][i] == 1）。for (int i = 1; i <= n; i++) {//如果存在邊，則將節點i添加到當前路徑path中，并遞歸調用dfs方法，以節點i作為新的當前節點。if (graph[x][i] == 1) {path.add(i);dfs(graph, i, n);path.remove(path.size() - 1);//在遞歸調用返回后，從當前路徑path中移除最后一個節點，為了回溯到上一個狀態，以便嘗試其他可能的路徑。}}}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);//使用Scanner類從標準輸入讀取數據。int n = scanner.nextInt();//首先讀取兩個整數n和m，分別代表圖中的節點數和邊數。int m = scanner.nextInt();int[][] graph = new int[n + 1][n + 1];//創建一個n+1乘以n+1的二維數組graph，初始化為0，代表無向圖的鄰接矩陣。for (int i = 0; i < m; i++) {//循環m次，每次讀取兩個整數s和t，代表一條邊的起點和終點，并將graph[s][t]和graph[t][s]設置為1，表示無向圖的邊。int s = scanner.nextInt();int t = scanner.nextInt();graph[s][t] = 1;}path.add(1);//將節點1添加到路徑path中，因為搜索從節點1開始。dfs(graph, 1, n);//從節點1開始，調用dfs方法尋找所有到節點n的路徑。if (result.isEmpty()) System.out.println(-1);//如果result為空，表示沒有找到任何路徑，輸出-1。否則，遍歷result中的每個路徑，并打印出來。對于每個路徑，除了最后一個節點外，其他節點后面都跟一個空格。for (List<Integer> pa : result) {for (int i = 0; i < pa.size() - 1; i++) {System.out.print(pa.get(i) + " ");}System.out.println(pa.get(pa.size() - 1));}}
}

?假設輸入如下：

這表示圖中有 4 個節點（n = 4），4 條邊，邊分別為?(1, 2)、(2, 3)、(3, 4)?和?(1, 3)。

1. 主方法?`main`?中的初始化操作

創建一個?5 x 5?的二維數組?graph?作為鄰接矩陣，初始值全為 0。

2. 構建鄰接矩陣

第一次循環：s = 1，t = 2，則?graph[1][2] = 1，graph[2][1] = 1。
第二次循環：s = 2，t = 3，則?graph[2][3] = 1，graph[3][2] = 1。
第三次循環：s = 3，t = 4，則?graph[3][4] = 1，graph[4][3] = 1。
第四次循環：s = 1，t = 3，則?graph[1][3] = 1，graph[3][1] = 1。

此時鄰接矩陣?graph?如下：

  0  1  2  3  40 [0, 0, 0, 0, 0]1 [0, 0, 1, 1, 0]2 [0, 1, 0, 1, 0]3 [0, 1, 1, 0, 1]4 [0, 0, 0, 1, 0]

3. 初始化路徑并開始深度優先搜索

將節點 1 添加到路徑?path?中，此時?path = [1]，然后調用?dfs?方法從節點 1 開始搜索到節點 4 的所有路徑。

4. 深度優先搜索?`dfs`?過程

第一次調用?`dfs(graph, 1, 4)`

當前節點?x = 1，目標節點?n = 4，x != n，進入?for?循環。
當?i = 2?時，graph[1][2] == 1，將節點 2 添加到?path?中，path = [1, 2]，遞歸調用?dfs(graph, 2, 4)。

第二次調用?`dfs(graph, 2, 4)`

當前節點?x = 2，目標節點?n = 4，x != n，進入?for?循環。
當?i = 3?時，graph[2][3] == 1，將節點 3 添加到?path?中，path = [1, 2, 3]，遞歸調用?dfs(graph, 3, 4)。

第三次調用?`dfs(graph, 3, 4)`

當前節點?x = 3，目標節點?n = 4，x != n，進入?for?循環。
當?i = 4?時，graph[3][4] == 1，將節點 4 添加到?path?中，path = [1, 2, 3, 4]。
此時?x == n，將?path?的副本?[1, 2, 3, 4]?添加到?result?中，result = [[1, 2, 3, 4]]，然后返回。
返回到?dfs(graph, 3, 4)?后，執行?path.remove(path.size() - 1)，path = [1, 2, 3]。

回到第二次調用?`dfs(graph, 2, 4)`

繼續?for?循環，沒有其他滿足?graph[2][i] == 1?的節點，執行?path.remove(path.size() - 1)，path = [1, 2]。
回到第一次調用?dfs(graph, 1, 4)。

第一次調用?`dfs(graph, 1, 4)`?繼續

當?i = 3?時，graph[1][3] == 1，將節點 3 添加到?path?中，path = [1, 3]，遞歸調用?dfs(graph, 3, 4)。

第四次調用?`dfs(graph, 3, 4)`

當前節點?x = 3，目標節點?n = 4，x != n，進入?for?循環。
當?i = 4?時，graph[3][4] == 1，將節點 4 添加到?path?中，path = [1, 3, 4]。
此時?x == n，將?path?的副本?[1, 3, 4]?添加到?result?中，result = [[1, 2, 3, 4], [1, 3, 4]]，然后返回。
返回到?dfs(graph, 3, 4)?后，執行?path.remove(path.size() - 1)，path = [1, 3]。

回到第一次調用?`dfs(graph, 1, 4)`

繼續?for?循環，沒有其他滿足?graph[1][i] == 1?的節點，執行?path.remove(path.size() - 1)，path = [1]。

5. 輸出結果

由于?result?不為空，會依次輸出?result?中的每個路徑：

1 2 3 4
1 3 4

通過以上步驟，我們可以清晰地看到代碼是如何利用深度優先搜索算法找出從節點 1 到節點 4 的所有路徑的。

4.廣度優先搜索理論基礎

在深度優先搜索的講解中，有深度優先搜索和廣度優先搜索的區別。

廣搜（bfs）是一圈一圈的搜索過程，和深搜（dfs）是一條路跑到黑然后再回溯。

廣搜的使用場景

廣搜的搜索方式就適合于解決兩個點之間的最短路徑問題。

因為廣搜是從起點出發，以起始點為中心一圈一圈進行搜索，一旦遇到終點，記錄之前走過的節點就是一條最短路。

當然，也有一些問題是廣搜和深搜都可以解決的，例如島嶼問題，這類問題的特征就是不涉及具體的遍歷方式，只要能把相鄰且相同屬性的節點標記上就行。

廣搜的過程

BFS是一圈一圈的搜索過程，但具體是怎么一圈一圈來搜呢。

我們用一個方格地圖，假如每次搜索的方向為上下左右（不包含斜上方），那么給出一個start起始位置，那么BFS就是從四個方向走出第一步。

如果加上一個end終止位置，那么使用BFS的搜索過程如圖所示：

我們從圖中可以看出，從start起點開始，是一圈一圈，向外搜索，方格編號1為第一步遍歷的節點，方格編號2為第二步遍歷的節點，第四步的時候我們找到終止點end。

正是因為BFS一圈一圈的遍歷方式，所以一旦遇到終止點，那么一定是一條最短路徑。

而且地圖還可以有障礙，如圖所示：

在第五步，第六步我只把關鍵的節點染色了，其他方向周邊沒有去染色，大家只要關注關鍵地方染色的邏輯就可以。

從圖中可以看出，如果添加了障礙，我們是第六步才能走到end終點。

只要BFS只要搜到終點一定是一條最短路徑。

5.島嶼數量

卡碼網題目鏈接（ACM模式）(opens new window)

題目描述：

給定一個由 1（陸地）和 0（水）組成的矩陣，你需要計算島嶼的數量。島嶼由水平方向或垂直方向上相鄰的陸地連接而成，并且四周都是水域。你可以假設矩陣外均被水包圍。

輸入描述：

第一行包含兩個整數 N, M，表示矩陣的行數和列數。

后續 N 行，每行包含 M 個數字，數字為 1 或者 0。

輸出描述：

輸出一個整數，表示島嶼的數量。如果不存在島嶼，則輸出 0。

輸入示例：

輸出示例：

提示信息

根據測試案例中所展示，島嶼數量共有 3 個，所以輸出 3。

數據范圍：

1 <= N, M <= 50

深搜（dfs）

public class Number_of_Islands_Depth_First_Search {public static int[][] dir ={{0,1},{1,0},{-1,0},{0,-1}};//二維數組，存儲了深度優先搜索中可以探索的四個方向：右（{0, 1}）、下（{1, 0}）、左（{-1, 0}）、上（{0, -1}）。在 DFS 過程中，通過這個數組可以方便地獲取當前單元格的相鄰單元格坐標。public static void dfs(boolean[][] visited,int x,int y ,int [][]grid) {//遞歸方法，用于執行深度優先搜索。boolean[][] visited 參數是一個與grid同樣大小的二維數組，用來標記某個單元格是否已經被訪問過。int x 和 int y 分別是當前單元格的行和列索引。int[][] grid 是輸入的二維數組，表示地圖，其中1表示陸地，0表示水域。for (int i = 0; i < 4; i++) {//對于當前單元格的每一個可能的相鄰單元格（右、下、左、上），遍歷四個方向，計算當前單元格在每個方向上的相鄰單元格坐標 nextX 和 nextY。int nextX=x+dir[i][0];int nextY=y+dir[i][1];if(nextY<0||nextX<0||nextX>= grid.length||nextY>=grid[0].length)//檢查相鄰單元格的坐標是否越界，如果越界則跳過該方向。continue;if(!visited[nextX][nextY]&&grid[nextX][nextY]==1)//若相鄰單元格未被訪問且為陸地（值為 1），則將其標記為已訪問，并遞歸調用 dfs 方法繼續探索該單元格的相鄰單元格。{visited[nextX][nextY]=true;dfs(visited,nextX,nextY,grid);}}}public static void main(String[] args) {Scanner sc = new Scanner(System.in);//使用Scanner類從標準輸入讀取數據。int m= sc.nextInt();//首先讀取兩個整數m和n，分別代表地圖的行數和列數。int n = sc.nextInt();int[][] grid = new int[m][n];//創建一個大小為 m x n 的二維數組 grid，并循環讀取 m x n 個整數填充該數組，這些整數表示地圖中每個單元格的狀態（0 或 1）。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];//創建一個大小為m x n的布爾二維數組visited，初始化為false，表示所有單元格都未被訪問。int ans = 0;//初始化一個整數ans用于存儲島嶼的數量。for (int i = 0; i < m; i++) {//遍歷grid中的每個單元格，對于每個值為1且未被訪問的單元格，執行以下操作：將ans加1，表示找到一個新島嶼。將該單元格標記為已訪問。調用dfs方法從該單元格開始搜索整個島嶼，將與該單元格相連的所有陸地單元格都標記為已訪問。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);}
}

假設輸入如下：

這表示地圖是一個 3 行 3 列的二維網格，具體的地圖內容為：

1 1 0
1 1 0
0 0 1

詳細執行步驟

1. 輸入讀取和初始化

根據輸入，grid?數組被初始化為：

[[1, 1, 0],[1, 1, 0],[0, 0, 1]
]

同時，創建一個?3 x 3?的布爾型二維數組?visited，初始值全為?false，表示所有單元格都未被訪問：

[[false, false, false],[false, false, false],[false, false, false]
]

并將島嶼數量?ans?初始化為 0。

2. 遍歷地圖并統計島嶼數量

第一次發現陸地

當?i = 0，j = 0?時，!visited[0][0]?為?true?且?grid[0][0] = 1，滿足條件：

ans?加 1，此時?ans = 1。
visited[0][0]?標記為?true。
調用?dfs(visited, 0, 0, grid)?開始深度優先搜索。

在?dfs?方法中：

對于方向?i = 0（右），nextX = 0 + 0 = 0，nextY = 0 + 1 = 1，nextX?和?nextY?未越界，且?!visited[0][1]?為?true?且?grid[0][1] = 1，則?visited[0][1]?標記為?true，遞歸調用?dfs(visited, 0, 1, grid)。
- 在?dfs(visited, 0, 1, grid)?中，繼續探索其相鄰單元格，最終會將第一行的兩個 1 以及第二行對應的兩個 1 都標記為已訪問。
其他方向可能會遇到越界或者不是陸地的情況，會跳過相應的探索。

第二次發現陸地

當?i = 2，j = 2?時，!visited[2][2]?為?true?且?grid[2][2] = 1，滿足條件：

ans?加 1，此時?ans = 2。
visited[2][2]?標記為?true。
調用?dfs(visited, 2, 2, grid)?開始深度優先搜索。由于這個 1 沒有相鄰的其他 1，所以在?dfs?方法中探索相鄰單元格時，不會再遞歸調用?dfs?方法。

3. 輸出結果

最終輸出?ans?的值為 2，表示地圖中有 2 個島嶼。

廣搜（bfs）

public class Number_of_Islands_Breadth_First_Search {static class pair {//pair 是一個靜態內部類，用于存儲二維網格中單元格的坐標。first 表示行坐標，second 表示列坐標。int first;int second;pair(int first, int second) {//構造函數 pair(int first, int second) 用于初始化坐標對。this.first = first;this.second = second;}}public static int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};//二維數組，存儲了廣度優先搜索中可以探索的四個方向：右（{0, 1}）、下（{1, 0}）、左（{0, -1}）、上（{-1, 0}）。在 BFS 過程中，通過這個數組可以方便地獲取當前單元格的相鄰單元格坐標。public static void bfs(int[][] grid, boolean[][] visited, int x, int y) {//方法，用于執行廣度優先搜索。int[][] grid 是輸入的二維數組，表示地圖，其中1表示陸地，0表示水域。boolean[][] visited 參數是一個與grid同樣大小的二維數組，用來標記某個單元格是否已經被訪問過。int x 和 int y 分別是當前單元格的行和列索引。Queue<pair> queue = new LinkedList<pair>();//創建一個隊列queue，用于存儲待訪問的坐標對。queue.add(new pair(x, y));//將起始坐標 (x, y) 封裝成 pair 對象添加到隊列中，并將該單元格標記為已訪問。visited[x][y] = true;while (!queue.isEmpty()) {//while 循環，只要隊列不為空：從隊列中取出隊首元素，獲取其行坐標 curX 和列坐標 curY。int curX = queue.peek().first;int curY = queue.poll().second;for (int i = 0; i < 4; i++) {//遍歷四個方向，計算當前單元格在每個方向上的相鄰單元格坐標 nextX 和 nextY。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) {//若相鄰單元格未被訪問且為陸地（值為 1），則將其封裝成 pair 對象添加到隊列中，并將該單元格標記為已訪問。queue.add(new pair(nextX, nextY));visited[nextX][nextY] = true;}}}}public static void main(String[] args) {Scanner sc = new Scanner(System.in);//創建一個 Scanner 對象，用于從標準輸入（通常是鍵盤）讀取數據。int m = sc.nextInt();//依次讀取兩個整數，分別賦值給 m 和 n，其中 m 表示地圖的行數，n 表示地圖的列數。int n = sc.nextInt();int[][] grid = new int[m][n];//創建一個大小為 m x n 的二維整數數組 grid，用于存儲地圖數據，其中 1 表示陸地，0 表示水域。boolean[][] visited = new boolean[m][n];//創建一個大小為m x n的布爾二維數組visited，初始化為false，表示所有單元格都未被訪問。int ans = 0;//初始化一個整數變量 ans，用于記錄地圖中島嶼的數量，初始值為 0。for (int i = 0; i < m; i++) {//循環讀取m x n個整數填充grid。for (int j = 0; j < n; j++) {grid[i][j] = sc.nextInt();}}for (int i = 0; i < m; i++) {//遍歷grid中的每個單元格，對于每個值為1且未被訪問的單元格，執行以下操作：將ans加1，表示找到一個新島嶼。調用 bfs 方法從當前單元格 (i, j) 開始進行廣度優先搜索，將與該單元格相連的所有陸地單元格標記為已訪問，這樣可以確保一個島嶼的所有陸地單元格只會被統計一次。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);}
}

假設輸入的二維數組grid為：

執行過程如下：

初始化visited數組，所有值為false，ans初始化為0。
遍歷grid，從左上角的(0,0)開始，發現grid[0][0]為1且未被訪問：
- ans加1，變為1。
- 調用bfs方法，將(0,0)加入隊列，標記為已訪問。
- 隊列不為空，開始循環：
  - 取出隊首元素(0,0)，遍歷其四個方向：
    - (0,1)為1且未訪問，加入隊列，標記為已訪問。
    - (1,0)為1且未訪問，加入隊列，標記為已訪問。
    - 其他方向越界或為0，跳過。
  - 取出隊首元素(0,1)，遍歷其四個方向：
    - (0,2)為0，跳過。
    - (1,1)為1且未訪問，加入隊列，標記為已訪問。
    - 其他方向越界或已訪問，跳過。
  - 取出隊首元素(1,0)，遍歷其四個方向：
    - (1,1)已訪問，跳過。
    - (2,0)為0，跳過。
    - 其他方向越界或已訪問，跳過。
  - 取出隊首元素(1,1)，遍歷其四個方向：
    - (1,2)為0，跳過。
    - (2,1)為0，跳過。
    - 其他方向越界或已訪問，跳過。
  - 隊列為空，BFS結束。
繼續遍歷grid，發現grid[2][2]為1且未被訪問：
- ans加1，變為2。
- 調用bfs方法，將(2,2)加入隊列，標記為已訪問。
- 隊列不為空，開始循環：
  - 取出隊首元素(2,2)，遍歷其四個方向：
    - (2,3)為0，跳過。
    - (3,2)為0，跳過。
    - 其他方向越界或已訪問，跳過。
  - 隊列為空，BFS結束。
繼續遍歷grid，發現grid[3][3]為1且未被訪問：
- ans加1，變為3。
- 調用bfs方法，將(3,3)加入隊列，標記為已訪問。
- 隊列不為空，開始循環：
  - 取出隊首元素(3,3)，遍歷其四個方向：
    - (3,4)為1且未訪問，加入隊列，標記為已訪問。
    - (4,3)越界，跳過。
    - 其他方向越界或已訪問，跳過。
  - 取出隊首元素(3,4)，遍歷其四個方向：
    - (3,5)越界，跳過。
    - (4,4)越界，跳過。
    - 其他方向越界或已訪問，跳過。
  - 隊列為空，BFS結束。
繼續遍歷grid，未發現新的未訪問且值為1的單元格，循環結束。
輸出ans，結果為3，表示該地圖中有三個島嶼。

6.?島嶼的最大面積

卡碼網題目鏈接（ACM模式）(opens new window)

題目描述

給定一個由 1（陸地）和 0（水）組成的矩陣，計算島嶼的最大面積。島嶼面積的計算方式為組成島嶼的陸地的總數。島嶼由水平方向或垂直方向上相鄰的陸地連接而成，并且四周都是水域。你可以假設矩陣外均被水包圍。

輸入描述

第一行包含兩個整數 N, M，表示矩陣的行數和列數。后續 N 行，每行包含 M 個數字，數字為 1 或者 0，表示島嶼的單元格。

輸出描述

輸出一個整數，表示島嶼的最大面積。如果不存在島嶼，則輸出 0。

輸入示例

輸出示例

提示信息

樣例輸入中，島嶼的最大面積為 4。

數據范圍：

1 <= M, N <= 50。

public class Max_Area_Island {static final int[][] dir={{0,1},{1,0},{0,-1},{-1,0}};//靜態常量二維數組，存儲了深度優先搜索中可以探索的四個方向，分別是右（{0, 1}）、下（{1, 0}）、左（{0, -1}）、上（{-1, 0}）。在 DFS 過程中，通過這個數組可以方便地獲取當前單元格的相鄰單元格坐標。static int result=0;//用于存儲最大島嶼的面積，初始值為 0。static int count=0;//用于在 DFS 過程中臨時記錄當前正在探索的島嶼的面積，初始值為 0。public static void main(String[] args){Scanner scanner = new Scanner(System.in);//使用 Scanner 類從標準輸入讀取地圖的行數 n 和列數 m。int n = scanner.nextInt();int m = scanner.nextInt();int[][] map = new int[n][m];//創建一個大小為 n x m 的二維整數數組 map，并通過兩層嵌套的 for 循環讀取 n x m 個整數填充該數組，這些整數表示地圖中每個單元格的狀態（0 或 1）。for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {map[i][j]=scanner.nextInt();}}boolean[][] visited = new boolean[n][m];//創建一個大小為 n x m 的二維布爾數組 visited，初始化為 false，用于標記地圖中每個單元格是否已經被訪問過。for (int i = 0; i < n; i++) {//使用兩層嵌套的 for 循環遍歷地圖的每個單元格。for (int j = 0; j < m; j++) {if(!visited[i][j]&&map[i][j]==1){//對于每個未被訪問過且值為 1 的單元格，將 count 重置為 0，表示開始計算一個新島嶼的面積。count=0;dfs(map,visited,i,j);//調用 dfs 方法從該單元格開始進行深度優先搜索，計算該島嶼的面積。result= Math.max(count, result);//搜索結束后，使用 Math.max(count, result) 更新 result 的值，確保 result 始終存儲最大島嶼的面積。}}}System.out.println(result);}public static void dfs(int[][] map,boolean[][] visited,int x,int y){//map：這是一個二維整數數組，代表整個地圖。其中 1 表示陸地，0 表示水域。visited：一個與 map 大小相同的二維布爾數組，用于標記每個單元格是否已經被訪問過。初始時，所有元素都為 false，表示所有單元格都未被訪問。x 和 y：表示當前正在訪問的單元格的行索引和列索引。count++;//每當進入 dfs 方法時，說明當前單元格 (x, y) 是陸地，因此將 count 加 1。count 是一個全局變量，用于記錄當前正在探索的島嶼的面積。visited[x][y]=true;//將當前單元格標記為已訪問，避免后續再次訪問該單元格，防止陷入無限循環。for (int i = 0; i < 4; i++) {//通過循環遍歷這四個方向，計算當前單元格 (x, y) 在每個方向上的相鄰單元格的坐標 (nextX, nextY)。int nextX=x+dir[i][0];int nextY=y+dir[i][1];if(nextX<0||nextY<0//檢查相鄰單元格的坐標是否越界（小于 0），如果越界則跳過。||nextX>=map.length||nextY>=map[0].length//檢查相鄰單元格的坐標是否超出地圖范圍，如果超出則跳過。||visited[nextX][nextY]||map[nextX][nextY]==0)continue;//檢查相鄰單元格是否已經被訪問過，如果已經訪問過則跳過。檢查相鄰單元格是否為水域（值為 0），如果是水域則跳過。dfs(map,visited,nextX,nextY);//如果相鄰單元格滿足繼續訪問的條件，則遞歸調用 dfs 方法，以該相鄰單元格為新的起始點繼續進行深度優先搜索。}}
}

假設輸入的地圖為：

執行過程如下：

初始化：
- map：輸入的地圖。
- visited：標記數組，初始值為false。
- result：最大島嶼面積，初始值為0。
- count：當前島嶼面積，初始值為0。
遍歷地圖：
- 遍歷到(0,0)，發現map[0][0]為1且未訪問：
  - 將count重置為0。
  - 調用dfs(map, visited, 0, 0)：
    - count加1，標記(0,0)為已訪問。
    - 遍歷四個方向，發現(0,1)和(1,0)為1且未訪問，遞歸調用dfs：
      - (0,1)：count加1，標記為已訪問，繼續遍歷四個方向，發現(1,1)為1且未訪問，遞歸調用dfs。
      - (1,1)：count加1，標記為已訪問，繼續遍歷四個方向，發現無符合條件的相鄰單元格。
      - (1,0)：count加1，標記為已訪問，繼續遍歷四個方向，發現無符合條件的相鄰單元格。
    - 最終，count為4，表示當前島嶼面積為4。
  - 更新result為Math.max(result, count)，即result=4。
- 繼續遍歷，發現(2,2)為1且未訪問：
  - 將count重置為0。
  - 調用dfs(map, visited, 2, 2)：
    - count加1，標記(2,2)為已訪問。
    - 遍歷四個方向，發現無符合條件的相鄰單元格。
  - 更新result為Math.max(result, count)，即result=4。
- 繼續遍歷，發現(3,3)為1且未訪問：
  - 將count重置為0。
  - 調用dfs(map, visited, 3, 3)：
    - count加1，標記(3,3)為已訪問。
    - 遍歷四個方向，發現(3,4)為1且未訪問，遞歸調用dfs。
    - (3,4)：count加1，標記為已訪問。
  - 更新result為Math.max(result, count)，即result=4。
輸出結果：
- 最終result為4，表示最大島嶼面積為4。

7.孤島的總面積

卡碼網：101. 孤島的總面積(opens new window)

題目描述

給定一個由 1（陸地）和 0（水）組成的矩陣，島嶼指的是由水平或垂直方向上相鄰的陸地單元格組成的區域，且完全被水域單元格包圍。孤島是那些位于矩陣內部、所有單元格都不接觸邊緣的島嶼。

現在你需要計算所有孤島的總面積，島嶼面積的計算方式為組成島嶼的陸地的總數。

輸入描述

第一行包含兩個整數 N, M，表示矩陣的行數和列數。之后 N 行，每行包含 M 個數字，數字為 1 或者 0。

輸出描述

輸出一個整數，表示所有孤島的總面積，如果不存在孤島，則輸出 0。

輸入示例

輸出示例：

提示信息：

在矩陣中心部分的島嶼，因為沒有任何一個單元格接觸到矩陣邊緣，所以該島嶼屬于孤島，總面積為 1。

數據范圍：

1 <= M, N <= 50。

public class Total_Area_of_Isolated_Islands {private static int count = 0;//用于存儲所有孤島的總面積，初始值為 0。private static final int[][] dir = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};//靜態常量二維數組，定義了四個方向的移動，分別對應右（{0, 1}）、下（{1, 0}）、上（{-1, 0}）、左（{0, -1}）。在 BFS 過程中，通過這個數組可以方便地獲取當前單元格的相鄰單元格坐標。private static void bfs(int[][] grid, int x, int y) {//私有靜態方法，用于執行廣度優先搜索。int[][] grid 是輸入的二維數組，表示地圖，其中1表示陸地，0表示水域。int x 和 int y 是當前單元格的坐標。Queue<int[]> que = new LinkedList<>();//創建一個隊列 que，將起始坐標 (x, y) 加入隊列，并將該單元格標記為已訪問（將 grid[x][y] 設置為 0）。同時，count 加 1，表示當前島嶼面積增加。que.add(new int[]{x, y});grid[x][y] = 0;count++;while (!que.isEmpty()) {//進入 while 循環，只要隊列不為空，就從隊列中取出一個坐標 (curx, cury)。int[] cur = que.poll();int curx = cur[0];int cury = cur[1];for (int i = 0; i < 4; i++) {//遍歷四個方向，計算相鄰單元格的坐標 (nextx, nexty)。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 (grid[nextx][nexty] == 1) {que.add(new int[]{nextx, nexty});//如果相鄰單元格是陸地（值為 1），將其加入隊列，count 加 1，并將該單元格標記為已訪問（將 grid[nextx][nexty] 設置為 0）。count++;grid[nextx][nexty] = 0;}}}}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();//使用Scanner類從標準輸入讀取數據。首先讀取兩個整數n和m，分別代表地圖的行數和列數。創建一個大小為n x m的二維數組grid，用于存儲地圖數據。循環讀取n x m個整數填充grid。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();}//接下來，程序檢查地圖的邊界上的陸地單元格，并對其執行BFS，以確保邊界上的陸地不被重復計算。重置count為0，然后遍歷整個地圖，對所有未訪問的陸地單元格執行BFS，計算每個孤島的面積。最后，輸出所有孤島的總面積。}//主要目的是將與地圖邊界相連的陸地全部標記為已訪問，這樣在后續計算孤立島嶼面積時，就不會把這些與邊界相連的陸地包含進去。for (int i = 0; i < n; i++) {//首先，通過外層的 for 循環遍歷地圖的左右邊界（即每一行的第一列和最后一列）。如果發現邊界上的單元格為陸地（值為 1），則調用 bfs 方法從該單元格開始進行廣度優先搜索。在 bfs 過程中，會將與該邊界陸地相連的所有陸地單元格標記為已訪問（將其值置為 0），同時會增加 count 的值。if (grid[i][0] == 1) bfs(grid, i, 0);if (grid[i][m - 1] == 1) bfs(grid, i, m - 1);}for (int j = 0; j < m; j++) {//接著，通過內層的 for 循環遍歷地圖的上下邊界（即第一行和最后一行的每一列）。同樣，如果發現邊界上的單元格為陸地，則調用 bfs 方法進行處理。if (grid[0][j] == 1) bfs(grid, 0, j);if (grid[n - 1][j] == 1) bfs(grid, n - 1, j);}count = 0;//由于之前調用 bfs 方法處理邊界陸地時，count 已經記錄了這些陸地的面積，而我們只關心孤立島嶼的面積，所以需要將 count 重置為 0，以便重新開始計算孤立島嶼的總面積。for (int i = 0; i < n; i++) {//使用嵌套的 for 循環遍歷整個地圖的每一個單元格。for (int j = 0; j < m; j++) {if (grid[i][j] == 1) bfs(grid, i, j);//如果發現某個單元格為陸地（值為 1），說明這是一個未被訪問過的孤立島嶼的一部分，調用 bfs 方法從該單元格開始進行廣度優先搜索。在 bfs 過程中，會將與該陸地單元格相連的所有陸地單元格標記為已訪問（將其值置為 0），同時會不斷增加 count 的值，從而計算出該孤立島嶼的面積。隨著遍歷的進行，會依次計算出所有孤立島嶼的面積并累加到 count 中。}}System.out.println(count);}
}

假設輸入的地圖為：

執行過程如下：

輸入地圖：
```
0 1 1 0 0
0 1 0 0 0
0 0 0 1 1
1 0 0 1 0
```
處理邊界陸地：
- 遍歷邊界，發現(0,1)、(0,2)、(3,0)和(3,3)是邊界上的陸地，調用bfs方法：
  - (0,1)和(0,2)相連，形成一個與邊界相連的陸地區域，面積為2。
  - (3,0)單獨一個陸地，面積為1。
  - (3,3)單獨一個陸地，面積為1。
- 處理后地圖變為：
```
0 0 0 0 0
0 0 0 0 0
0 0 0 1 1
0 0 0 0 0
```
計算孤立島嶼面積：
- 重置count為0。
- 遍歷地圖，發現(2,3)和(2,4)是孤立島嶼的一部分，調用bfs方法：
  - (2,3)和(2,4)相連，形成一個孤立島嶼，面積為2。
- 最終count為2。
輸出結果：
- 孤立島嶼的總面積為2。

8.沉沒孤島

卡碼網題目鏈接（ACM模式）(opens new window)

題目描述：

現在你需要將所有孤島“沉沒”，即將孤島中的所有陸地單元格（1）轉變為水域單元格（0）。

輸入描述：

第一行包含兩個整數 N, M，表示矩陣的行數和列數。

之后 N 行，每行包含 M 個數字，數字為 1 或者 0，表示島嶼的單元格。

輸出描述

輸出將孤島“沉沒”之后的島嶼矩陣。

輸入示例：

輸出示例：

提示信息：

將孤島沉沒：

數據范圍：

1 <= M, N <= 50

public class Sunken_Island {static int[][] dir = { {-1, 0}, {0, -1}, {1, 0}, {0, 1} };//靜態二維數組，定義了四個方向的移動，分別對應上（{-1, 0}）、左（{0, -1}）、下（{1, 0}）、右（{0, 1}）。在深度優先搜索（DFS）過程中，通過這個數組可以方便地獲取當前單元格的相鄰單元格坐標。public static void dfs(int[][] grid, int x, int y) {//一個遞歸方法，用于深度優先搜索。int[][] grid 是輸入的二維數組，表示地圖。int x 和 int y 是當前單元格的坐標。grid[x][y] = 2;//先將當前土地格標記為2，表示已訪問。for (int[] d : dir) {//遍歷四個方向，計算當前單元格在每個方向上的相鄰單元格坐標 (nextX, nextY)。int nextX = x + d[0];int nextY = y + d[1];if (nextX < 0 || nextX >= grid.length || nextY < 0 || nextY >= grid[0].length) continue;//檢查相鄰單元格的坐標是否越界，如果越界則跳過該方向。if (grid[nextX][nextY] == 0 || grid[nextX][nextY] == 2) continue;//檢查相鄰單元格是否為水域（值為 0）或已訪問的土地（值為 2），如果是則跳過該方向。dfs(grid, nextX, nextY);//如果相鄰單元格是未訪問的陸地（值為 1），則遞歸調用 dfs 方法繼續搜索。}}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);//使用Scanner類從標準輸入讀取數據。首先讀取兩個整數n和m，分別代表地圖的行數和列數。創建一個大小為n x m的二維數組grid，用于存儲地圖數據。循環讀取n x m個整數填充grid。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();}}for (int i = 0; i < n; i++) {//遍歷地圖的左右邊界（即每一行的第一列和最后一列）。如果邊界上的單元格為陸地（值為 1），則調用 dfs 方法從該單元格開始進行深度優先搜索。在 dfs 過程中，會將與該邊界陸地相連的所有陸地單元格標記為 2，表示這些陸地與邊界相連。if (grid[i][0] == 1) dfs(grid, i, 0);if (grid[i][m - 1] == 1) dfs(grid, i, m - 1);}for (int j = 0; j < m; j++) {//第二個 for 循環遍歷地圖的上下邊界（即第一行和最后一行的每一列）。同樣，如果邊界上的單元格為陸地，則調用 dfs 方法進行處理。if (grid[0][j] == 1) dfs(grid, 0, j);if (grid[n - 1][j] == 1) dfs(grid, n - 1, j);}for (int i = 0; i < n; i++) {//使用嵌套的 for 循環遍歷整個地圖的每一個單元格。for (int j = 0; j < m; j++) {if (grid[i][j] == 1) grid[i][j] = 0;//如果單元格的值為 1，說明它是不與邊界相連的陸地（孤島），將其值置為 0，表示將其 “沉沒” 為水域。if (grid[i][j] == 2) grid[i][j] = 1;//如果單元格的值為 2，說明它是之前標記的與邊界相連的陸地，將其值恢復為 1。}}for (int i = 0; i < n; i++) {//使用嵌套的 for 循環遍歷處理后的地圖，將每個單元格的值輸出，同一行的單元格用空格分隔，不同行換行輸出，從而展示出處理后的地圖布局。for (int j = 0; j < m; j++) {System.out.print(grid[i][j] + " ");}System.out.println();}scanner.close();//關閉 Scanner 對象，釋放相關資源，避免資源泄漏。}
}

假設輸入的地圖為：

執行過程如下：

輸入地圖：
```
1 1 0 0 0
1 1 0 0 0
0 0 1 1 0
0 0 1 1 0
```
處理邊界陸地：
- 遍歷邊界，發現(0,0)和(0,1)是邊界上的陸地，調用dfs方法：
  - (0,0)和(0,1)相連，形成一個與邊界相連的陸地區域，將其標記為2。
- 處理后地圖變為：
```
2 2 0 0 0
2 2 0 0 0
0 0 1 1 0
0 0 1 1 0
```
處理內部孤島：
- 遍歷地圖，發現(2,2)和(2,3)是未標記的陸地（值為1），將其標記為0（表示“沉沒”）。
- 處理后地圖變為：
```
2 2 0 0 0
2 2 0 0 0
0 0 0 0 0
0 0 0 0 0
```
恢復邊界標記：
- 將值為2的單元格恢復為1：
```
1 1 0 0 0
1 1 0 0 0
0 0 0 0 0
0 0 0 0 0
```
輸出結果：
- 最終地圖為：
```
1 1 0 0 0
1 1 0 0 0
0 0 0 0 0
0 0 0 0 0
```

9.水流問題

卡碼網題目鏈接（ACM模式）(opens new window)

題目描述：

現有一個 N × M 的矩陣，每個單元格包含一個數值，這個數值代表該位置的相對高度。矩陣的左邊界和上邊界被認為是第一組邊界，而矩陣的右邊界和下邊界被視為第二組邊界。

矩陣模擬了一個地形，當雨水落在上面時，水會根據地形的傾斜向低處流動，但只能從較高或等高的地點流向較低或等高并且相鄰（上下左右方向）的地點。我們的目標是確定那些單元格，從這些單元格出發的水可以達到第一組邊界和第二組邊界。

輸入描述：

第一行包含兩個整數 N 和 M，分別表示矩陣的行數和列數。

后續 N 行，每行包含 M 個整數，表示矩陣中的每個單元格的高度。

輸出描述：

輸出共有多行，每行輸出兩個整數，用一個空格隔開，表示可達第一組邊界和第二組邊界的單元格的坐標，輸出順序任意。

輸入示例：

輸出示例：

提示信息：

圖中的藍色方塊上的雨水既能流向第一組邊界，也能流向第二組邊界。所以最終答案為所有藍色方塊的坐標。

數據范圍：

1 <= M, N <= 50

public class Water_Flow_Problem {public static void dfs(int[][] heights, int x, int y, boolean[][] visited, int preH) {//遞歸方法，用于執行深度優先搜索。int[][] heights 是輸入的二維數組，表示地形的高度圖。int x 和 int y 是當前單元格的坐標。boolean[][] visited 是一個布爾數組，用來標記某個單元格是否已經被訪問過。int preH 是前一個單元格的高度，用于判斷當前單元格是否為低洼地帶，即水流可以流向的地方。if (x < 0 || x >= heights.length || y < 0 || y >= heights[0].length || visited[x][y]) return;//檢查當前坐標是否越界或已被訪問，如果是，則返回。if (heights[x][y] < preH) return;//檢查當前單元格的高度是否小于前一個單元格的高度（heights[x][y] < preH），如果是，說明水流不能從當前單元格流向該方向，直接返回。visited[x][y] = true;//如果上述條件都不滿足，將當前單元格標記為已訪問dfs(heights, x + 1, y, visited, heights[x][y]);//遞歸地對當前單元格的四個相鄰單元格（下、上、右、左）進行深度優先搜索，同時將當前單元格的高度作為下一次遞歸的 preH。dfs(heights, x - 1, y, visited, heights[x][y]);dfs(heights, x, y + 1, visited, heights[x][y]);dfs(heights, x, y - 1, visited, heights[x][y]);}public static void main(String[] args) {Scanner sc = new Scanner(System.in);//使用Scanner類從標準輸入讀取數據。首先讀取兩個整數m和n，分別代表地圖的行數和列數。創建一個大小為m x n的二維數組heights，用于存儲地圖的高度數據。循環讀取m x n個整數填充heights。創建兩個布爾數組pacific和atlantic，分別用來標記單元格是否能夠被太平洋和大西洋流入，初始值都為 false。int m = sc.nextInt();int n = sc.nextInt();int[][] heights = new int[m][n];for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {heights[i][j] = sc.nextInt();}//對地圖的所有邊界單元格執行DFS，從太平洋（左邊界和上邊界）開始，將能夠流入的單元格標記為true在pacific數組中；從大西洋（右邊界和下邊界）開始，將能夠流入的單元格標記為true在atlantic數組中。}boolean[][] pacific = new boolean[m][n];boolean[][] atlantic = new boolean[m][n];for (int i = 0; i < m; i++) {//對于左邊界（列索引為 0）的每個單元格 (i, 0)，調用 dfs 方法進行深度優先搜索。傳入的 preH 為 Integer.MIN_VALUE，這確保邊界單元格一定能被訪問，因為任何單元格的高度都大于或等于 Integer.MIN_VALUE。在搜索過程中，如果某個單元格的水流可以從太平洋邊界流到，就將 pacific 數組中對應位置標記為 true。dfs(heights, i, 0, pacific, Integer.MIN_VALUE);dfs(heights, i, n - 1, atlantic, Integer.MIN_VALUE);//對于上邊界（行索引為 0）的每個單元格 (0, j)，同樣調用 dfs 方法進行搜索，并標記相應單元格。}for (int j = 0; j < n; j++) {//對于右邊界（列索引為 n - 1）的每個單元格 (i, n - 1)，調用 dfs 方法進行深度優先搜索，若某個單元格的水流可以從大西洋邊界流到，就將 atlantic 數組中對應位置標記為 true。dfs(heights, 0, j, pacific, Integer.MIN_VALUE);dfs(heights, m - 1, j, atlantic, Integer.MIN_VALUE);//對于下邊界（行索引為 m - 1）的每個單元格 (m - 1, j)，進行同樣的搜索和標記操作。}List<List<Integer>> res = new ArrayList<>();//創建一個列表res，用于存儲同時能夠被太平洋和大西洋流入的單元格的坐標。for (int i = 0; i < m; i++) {//使用兩層嵌套的 for 循環遍歷整個 heights 數組，檢查 pacific 和 atlantic 數組中對應位置的元素。for (int j = 0; j < n; j++) {if (pacific[i][j] && atlantic[i][j]) {//如果兩個數組中該位置都為 true，說明該單元格的水流既可以到達太平洋，也可以到達大西洋，將該單元格的坐標 (i, j) 封裝成 List<Integer> 并添加到 res 列表中。res.add(Arrays.asList(i, j));}}}//遍歷整個地圖，如果一個單元格在pacific和atlantic數組中都被標記為true，則將其坐標添加到res列表中。最后，遍歷res列表，打印出所有同時能夠被太平洋和大西洋流入的單元格的坐標。for (List<Integer> list : res) {//這是一個增強 for 循環，用于遍歷列表 res 中的每個元素。res 是一個 List<List<Integer>> 類型的列表，其中每個內部列表 list 都存儲著一個單元格的坐標（行索引和列索引）。for (int k = 0; k < list.size(); k++) {//遍歷內部列表 list 中的每個元素。list 中通常包含兩個元素，分別是單元格的行索引和列索引。if (k == 0) {System.out.print(list.get(k) + " ");//當 k 等于 0 時，意味著當前正在處理內部列表 list 的第一個元素（即單元格的行索引）。此時，將該元素的值輸出，并在后面添加一個空格，以符合輸出格式要求。} else {System.out.print(list.get(k));//當 k 不等于 0 時，意味著當前正在處理內部列表 list 的第二個元素（即單元格的列索引）。此時，直接將該元素的值輸出，不添加額外的空格。}}System.out.println();//在外層循環的每次迭代結束后，使用 System.out.println() 輸出一個換行符，這樣每個單元格的坐標會單獨占一行輸出，使輸出結果更加清晰易讀。}}
}

“水流問題” 里，太平洋和大西洋并非現實地理意義上的海洋，而是一種概念化的設定，用于表示地圖的特定邊界區域，以此模擬水流的流向。具體定義如下：

太平洋

在該問題的設定里，太平洋代表地圖的左邊界和上邊界。可以想象，水從這些邊界開始，能順著地勢（高度不降低）向地圖內部流動。代碼里通過從左邊界（列索引為 0）和上邊界（行索引為 0）的各個單元格出發進行深度優先搜索（DFS），來標記那些水流可以從太平洋邊界流到的內部單元格。

例如，對于一個?m x n?的地圖：

左邊界的單元格坐標為?(i, 0)，其中?i?的取值范圍是從 0 到?m - 1。
上邊界的單元格坐標為?(0, j)，其中?j?的取值范圍是從 0 到?n - 1。

大西洋

大西洋代表地圖的右邊界和下邊界。同樣地，水從這些邊界開始，能順著地勢向地圖內部流動。代碼里從右邊界（列索引為?n - 1）和下邊界（行索引為?m - 1）的各個單元格出發進行深度優先搜索，標記那些水流可以從大西洋邊界流到的內部單元格。

具體來說：

右邊界的單元格坐標為?(i, n - 1)，其中?i?的取值范圍是從 0 到?m - 1。
下邊界的單元格坐標為?(m - 1, j)，其中?j?的取值范圍是從 0 到?n - 1。

假設輸入的高度圖為：

執行過程如下：

輸入高度圖：

從太平洋邊界開始DFS：
- 太平洋邊界包括左邊界（列索引為0）和上邊界（行索引為0）。
- 對左邊界和上邊界的每個單元格調用dfs方法，將能夠流入太平洋的單元格標記為true在pacific數組中。
- 例如，從(0,0)開始，水流可以流向(0,1)、(1,0)等單元格，這些單元格在pacific數組中標記為true。
從大西洋邊界開始DFS：
- 大西洋邊界包括右邊界（列索引為n-1）和下邊界（行索引為m-1）。
- 對右邊界和下邊界的每個單元格調用dfs方法，將能夠流入大西洋的單元格標記為true在atlantic數組中。
- 例如，從(4,4)開始，水流可以流向(3,4)、(4,3)等單元格，這些單元格在atlantic數組中標記為true。
查找同時流入兩個大洋的單元格：
- 遍歷整個高度圖，檢查pacific和atlantic數組中對應位置的元素。
- 如果兩個數組中某位置都為true，說明該單元格的水流既可以到達太平洋，也可以到達大西洋，將其坐標添加到結果列表中。
- 在這個示例中，滿足條件的單元格包括(0,4)、(1,3)、(2,2)、(3,1)和(4,0)。
輸出結果：
- 輸出滿足條件的單元格坐標：
```
0 4
1 3
2 2
3 1
4 0
```

10.建造最大島嶼

卡碼網題目鏈接（ACM模式）(opens new window)

題目描述：

給定一個由 1（陸地）和 0（水）組成的矩陣，你最多可以將矩陣中的一格水變為一塊陸地，在執行了此操作之后，矩陣中最大的島嶼面積是多少。

島嶼面積的計算方式為組成島嶼的陸地的總數。島嶼是被水包圍，并且通過水平方向或垂直方向上相鄰的陸地連接而成的。你可以假設矩陣外均被水包圍。

輸入描述：

第一行包含兩個整數 N, M，表示矩陣的行數和列數。之后 N 行，每行包含 M 個數字，數字為 1 或者 0，表示島嶼的單元格。

輸出描述：

輸出一個整數，表示最大的島嶼面積。

輸入示例：

輸出示例

提示信息

對于上面的案例，有兩個位置可將 0 變成 1，使得島嶼的面積最大，即 6。

數據范圍：

1 <= M, N <= 50。

public class Maximize_the_Area_of_an_Island {static int count;//用于在深度優先搜索（DFS）過程中計數當前島嶼的大小。static int mark;//用于標記新發現的島嶼，初始值為 2，后續每發現一個新島嶼，mark 的值就會加 1，這樣可以在哈希表中區分不同的島嶼。static int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};//定義了四個方向的移動，分別對應右（{0, 1}）、左（{0, -1}）、下（{1, 0}）、上（{-1, 0}），用于在 DFS 過程中遍歷相鄰單元格。public static void dfs(int[][] grid, int x, int y, boolean[][] visited) {//遞歸方法，用于執行深度優先搜索，計算單個島嶼的面積。int[][] grid 是輸入的二維數組，表示地圖。int x 和 int y 是當前單元格的坐標。boolean[][] visited 是一個布爾數組，用來標記某個單元格是否已經被訪問過。if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length) return;//檢查當前坐標是否越界或該單元格是否已經被訪問過，或者該單元格是否為水域（值為 0），如果是，則直接返回。if (visited[x][y] || grid[x][y] == 0) return;visited[x][y] = true;//如果當前單元格是陸地（grid[x][y] == 1），則將其標記為已訪問，并增加島嶼計數。count++;grid[x][y] = mark;//將當前單元格的值更新為 mark，表示該單元格屬于當前標記的島嶼。dfs(grid, x, y + 1, visited);//遞歸地對當前單元格的四個相鄰單元格進行深度優先搜索。dfs(grid, x, y - 1, visited);dfs(grid, x + 1, y, visited);dfs(grid, x - 1, y, visited);}public static void main (String[] args) {Scanner sc = new Scanner(System.in);//使用Scanner類從標準輸入讀取數據。首先讀取兩個整數m和n，分別代表地圖的行數和列數。創建一個大小為m x n的二維數組grid，用于存儲地圖數據。循環讀取m x n個整數填充grid。初始化mark為2，用于標記不同的島嶼。visited數組用于記錄每個單元格是否已經被訪問過。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();}}mark = 2;boolean[][] visited = new boolean[m][n];HashMap<Integer, Integer> getSize = new HashMap<>();//創建一個HashMap<Integer, Integer> getSize用于存儲每個島嶼的標記和對應的面積，鍵為島嶼標記，值為島嶼面積。HashSet<Integer> set = new HashSet<>();//創建一個HashSet<Integer> set來存儲已經考慮過的島嶼標記，避免重復計算。boolean isAllIsland = true;//初始化為 true，用于判斷整個地圖是否全是陸地。for (int i = 0; i < m; i++) {//遍歷地圖計算每個島嶼的面積for (int j = 0; j < n; j++) {if (grid[i][j] == 0) isAllIsland = false;//如果遇到值為 0 的單元格（水域），則將 isAllIsland 置為 false。if (grid[i][j] == 1) {//當遇到值為 1 的單元格（陸地）時：將 count 重置為 0，用于統計當前島嶼的面積。count = 0;dfs(grid, i, j, visited);//調用 dfs 方法從該單元格開始進行深度優先搜索，計算當前島嶼的面積，搜索過程中會將該島嶼的所有單元格標記為已訪問，并將其標記為當前的 mark 值。getSize.put(mark, count);//將當前島嶼的面積 count 存入 getSize 中，鍵為當前的 mark 值。mark++;//mark 加 1，為下一個新島嶼的標記做準備。}}}int result = 0;//初始化result為0，用于存儲最大可能的島嶼面積。如果整個網格都是陸地（即isAllIsland為true），則最大島嶼面積就是整個網格的面積。if (isAllIsland) result =  m * n;for (int i = 0; i < m; i++) {//遍歷整個地圖，對每個水單元格，檢查將其變為陸地后，周圍島嶼的總面積，并更新result。最后，輸出計算出的最大島嶼面積。for (int j = 0; j < n; j++) {if (grid[i][j] == 0) {set.clear();//set 是一個 HashSet<Integer>，用于存儲已經考慮過的島嶼標記，避免重復計算。在處理每個新的水域單元格之前，需要清空 set，確保它只記錄當前水域單元格周圍島嶼的標記。int curSize = 1;//將 curSize 初始化為 1，表示將當前水域單元格變為陸地后，該單元格本身算一個面積單位。for (int[] dir : dirs) {//檢查當前水域單元格的四個相鄰單元格int curRow = i + dir[0];//算當前水域單元格 (i, j) 在四個方向上相鄰單元格的坐標 (curRow, curCol)。int curCol = j + dir[1];if (curRow < 0 || curRow >= m || curCol < 0 || curCol >= n) continue;//檢查相鄰單元格的坐標是否越界，如果越界（即 curRow < 0 或 curRow >= m 或 curCol < 0 或 curCol >= n），則跳過該相鄰單元格，繼續檢查下一個方向。int curMark = grid[curRow][curCol];//獲取相鄰單元格所屬島嶼的標記。在之前的 DFS 過程中，每個島嶼的單元格都被標記為同一個唯一的 mark 值。if (set.contains(curMark) || !getSize.containsKey(curMark)) continue;//如果 set 中已經包含了該標記，說明這個島嶼已經在本次計算中被考慮過，避免重復計算，跳過該島嶼。如果 getSize 中不包含該標記，說明這個單元格可能是水域或者是之前未處理的特殊情況，也跳過該單元格。set.add(curMark);//如果該島嶼標記未被考慮過，將其添加到 set 中，表示該島嶼已經被納入本次計算。curSize += getSize.get(curMark);//從 getSize 中獲取該島嶼的面積，并累加到 curSize 中，更新當前將該水域單元格變為陸地后相連島嶼的總面積。}result = Math.max(result, curSize);//使用 Math.max 函數比較當前計算得到的 curSize 和之前記錄的最大島嶼面積 result，將較大的值更新為新的 result。}}}System.out.println(result);//當遍歷完所有的水域單元格后，result 中存儲的就是將一個水域單元格變為陸地后能夠得到的最大島嶼面積，將其輸出。}
}

假設輸入的地圖為：

1.?輸入地圖并初始化

輸入地圖：

初始化mark為2，visited數組用于標記訪問狀態。

2.?計算每個島嶼的面積

遍歷地圖：從左到右、從上到下遍歷每個單元格。
遇到陸地單元格（值為1）：
- 重置count為0。
- 調用dfs方法，從該單元格開始深度優先搜索，計算當前島嶼的面積，并將島嶼的所有單元格標記為當前的mark值。
- 將當前島嶼的面積存入getSize哈希表中，鍵為mark值。
示例中的島嶼：
- 第一個島嶼（左上角）面積為3，標記為2。
- 第二個島嶼（右下角）面積為3，標記為3。

3.?檢查水域單元格并計算最大可能面積

遍歷地圖：再次遍歷地圖，這次關注值為0的單元格（水域）。
對于每個水域單元格：
- 清空set，用于存儲周圍島嶼的標記。
- 初始化curSize為1，表示將當前水域單元格變為陸地后的初始面積。
- 檢查四個相鄰單元格：
  - 如果相鄰單元格是陸地（值不為0），且其標記未在set中出現過，則將其面積累加到curSize中，并將該標記加入set。
示例中的計算：
- 假設將(1,2)（值為0）變為陸地：
  - 其左邊是島嶼2（面積3），右邊是島嶼3（面積3）。
  - curSize = 1（自身）+ 3（島嶼2）+ 3（島嶼3）= 7。
- 遍歷所有水域單元格后，更新result為最大值。

4.?特殊情況處理

如果整個地圖都是陸地（isAllIsland為true），則最大面積為整個地圖的面積。

5.?輸出結果

最終輸出result，即通過將一個水域單元格變為陸地后能夠形成的最大島嶼面積。

示例輸出

對于輸入地圖：

最大可能的島嶼面積為7。

11.字符串接龍

卡碼網題目鏈接（ACM模式）(opens new window)

題目描述

字典 strList 中從字符串 beginStr 和 endStr 的轉換序列是一個按下述規格形成的序列：

序列中第一個字符串是 beginStr。
序列中最后一個字符串是 endStr。
每次轉換只能改變一個字符。
轉換過程中的中間字符串必須是字典 strList 中的字符串。

給你兩個字符串 beginStr 和 endStr 和一個字典 strList，找到從 beginStr 到 endStr 的最短轉換序列中的字符串數目。如果不存在這樣的轉換序列，返回 0。

輸入描述

第一行包含一個整數 N，表示字典 strList 中的字符串數量。第二行包含兩個字符串，用空格隔開，分別代表 beginStr 和 endStr。后續 N 行，每行一個字符串，代表 strList 中的字符串。

輸出描述

輸出一個整數，代表從 beginStr 轉換到 endStr 需要的最短轉換序列中的字符串數量。如果不存在這樣的轉換序列，則輸出 0。

輸入示例

6
abc def
efc
dbc
ebc
dec
dfc
yhn

輸出示例

提示信息

從 startStr 到 endStr，在 strList 中最短的路徑為 abc -> dbc -> dec -> def，所以輸出結果為 4

數據范圍：

2 <= N <= 500

這個單詞轉換問題的廣度優先搜索（BFS）算法實現中，在?visitMap?里記錄新單詞的步數時要將當前步數加 1，這與 BFS 算法的特性以及問題的本質相關，下面為你詳細解釋：

1. BFS 算法特性

廣度優先搜索是一種按層遍歷的算法，它從起始節點開始，逐層地向外擴展搜索。每一層的節點距離起始節點的步數是相同的，并且下一層節點距離起始節點的步數比當前層節點多 1。

在這個單詞轉換問題里，隊列?queue?存儲著待處理的單詞，每次從隊列中取出一個單詞?curWord?進行處理，就相當于在當前層。然后通過改變?curWord?中的一個字母生成新單詞?newWord，這些新單詞屬于下一層。因為 BFS 是逐層擴展的，所以新單詞距離起始單詞的步數自然要比當前單詞多 1。

2. 問題本質

問題要求計算從起始單詞?beginWord?轉換到目標單詞?endWord?的最短轉換序列長度，每次轉換只能改變一個字母。這意味著每進行一次有效的轉換，轉換的步數就會增加 1。

當從當前單詞?curWord?生成新單詞?newWord?時，相當于進行了一次有效的轉換。所以，新單詞?newWord?距離起始單詞的步數應該是當前單詞?curWord?距離起始單詞的步數加上 1。

假設起始單詞是?"hit"，目標單詞是?"cog"，單詞列表包含?"hot"、"dot"、"dog"、"lot"、"log"、"cog"。

起始時，beginWord = "hit"，visitMap.put("hit", 1)，表示?"hit"?距離自身的步數為 1。
從?"hit"?可以生成?"hot"，此時?"hot"?距離?"hit"?的步數為?"hit"?的步數（1）加 1，即 2，所以?visitMap.put("hot", 2)。
從?"hot"?可以生成?"dot"?和?"lot"，它們距離?"hit"?的步數為?"hot"?的步數（2）加 1，即 3，所以?visitMap.put("dot", 3)?和?visitMap.put("lot", 3)。

以此類推，通過不斷地生成新單詞并記錄步數，最終可以找到從起始單詞到目標單詞的最短轉換序列長度。

這個單詞轉換問題的情境里，把起始單詞?"hit"?距離自身的步數設為 1，主要是為了符合問題中對于轉換序列長度的定義，方便后續統一計算和處理，下面詳細解釋原因：

1. 轉換序列長度的定義

題目要求計算從起始單詞?beginWord?轉換到目標單詞?endWord?的最短轉換序列長度。轉換序列長度指的是從起始單詞開始，經過一系列每次改變一個字母的轉換步驟，最終到達目標單詞所經過的單詞數量（包含起始單詞和目標單詞）。

當從起始單詞開始時，起始單詞本身就算作轉換序列中的第一個單詞，所以它距離自身的步數定義為 1。如果將起始單詞距離自身的步數定義為 0，那么最終得到的轉換序列長度就會比實際的轉換序列少一個單詞，不符合題目的要求。

2. 方便后續計算

在廣度優先搜索（BFS）算法的實現中，每一次從當前單詞生成新單詞時，新單詞距離起始單詞的步數是基于當前單詞的步數加 1 得到的。如果起始單詞的步數為 1，那么后續生成的新單詞的步數計算就會很直觀和統一。

例如，從起始單詞?"hit"?開始，生成了新單詞?"hot"，因為?"hot"?是通過?"hit"?改變一個字母得到的，所以?"hot"?距離?"hit"?的步數就是?"hit"?的步數（1）加 1，即 2。這樣的計算方式使得整個轉換過程中步數的計算邏輯清晰，易于理解和實現。

public class String_Consecutive {public static int ladderLength(String beginWord, String endWord, List<String> wordList) {//公共靜態方法，用于計算從beginWord到endWord的最短轉換序列長度。String beginWord 和 String endWord 分別是起始單詞和目標單詞。List<String> wordList 是包含所有有效單詞的列表。HashSet<String> set = new HashSet<>(wordList);//將wordList轉換為HashSet，以便快速檢查一個單詞是否存在于列表中。Queue<String> queue = new LinkedList<>();//創建一個Queue<String> queue用于存儲待處理的單詞，以及一個HashMap<String, Integer> visitMap用于存儲每個單詞到起始單詞的距離（即轉換步數）。HashMap<String, Integer> visitMap = new HashMap<>();queue.offer(beginWord);//初始時，將beginWord加入隊列，并在visitMap中記錄其步數為1。visitMap.put(beginWord, 1);while (!queue.isEmpty()) {//在循環中，只要隊列不為空，就不斷取出隊列頭部的單詞（curWord），并獲取其對應的步數（path）。該單詞到起始單詞的步數。String curWord = queue.poll();int path = visitMap.get(curWord);for (int i = 0; i < curWord.length(); i++) {//遍歷當前單詞的每個字母位置。char[] ch = curWord.toCharArray();//將當前單詞轉換為字符數組，方便修改字母。for (char k = 'a'; k <= 'z'; k++) {//對于curWord中的每個字母位置，生成所有可能的單詞（通過替換當前字母為a到z），并檢查每個新生成的單詞：如果新單詞等于endWord，則返回當前步數加1，因為這表示找到了最短路徑。如果新單詞存在于HashSet中且未被訪問過，則將其加入隊列，并在visitMap中記錄其步數。ch[i] = k;//替換當前字母位置的字母。String newWord = new String(ch);//將字符數組轉換為新的單詞。if (newWord.equals(endWord)) return path + 1;//如果新單詞等于目標單詞 endWord，說明找到了最短路徑，返回當前步數加 1。if (set.contains(newWord) && !visitMap.containsKey(newWord)) {//如果新單詞存在于 set 中且未被訪問過（即 visitMap 中不包含該單詞），則將其加入隊列，并在 visitMap 中記錄其步數為當前步數加 1。visitMap.put(newWord, path + 1);queue.offer(newWord);}}}}return 0;//如果隊列遍歷完后仍未找到目標單詞，返回 0，表示無法從起始單詞轉換到目標單詞。}public static void main (String[] args) {Scanner sc = new Scanner(System.in);//使用Scanner類從標準輸入讀取數據。首先讀取一個整數N，表示wordList中的單詞數量。讀取兩個單詞beginWord和endWord。循環讀取N個單詞填充wordList。調用ladderLength方法計算最短轉換序列長度，并輸出結果。int N = sc.nextInt();sc.nextLine();//消耗掉 nextInt() 之后的換行符。因為 nextInt() 方法只讀取整數，不會消耗換行符，而后續使用 nextLine() 讀取字符串時，如果不消耗這個換行符，會導致 nextLine() 讀取到空字符串。String[] strs = sc.nextLine().split(" ");//sc.nextLine()：讀取一行輸入，這一行包含起始單詞和目標單詞，它們之間用空格分隔。split(" ")：將讀取的字符串按空格分割成字符串數組 strs，strs[0] 就是起始單詞 beginWord，strs[1] 就是目標單詞 endWord。List<String> wordList = new ArrayList<>();for (int i = 0; i < N; i++) {wordList.add(sc.nextLine());//sc.nextLine()：在每次循環中，讀取一行輸入，這一行是一個單詞，然后將其添加到 wordList 列表中。}int result = ladderLength(strs[0], strs[1], wordList);//調用 ladderLength 方法，傳入起始單詞 strs[0]、目標單詞 strs[1] 和單詞列表 wordList，計算從起始單詞到目標單詞的最短轉換序列長度，并將結果存儲在變量 result 中。System.out.println(result);}
}

假設輸入的單詞列表和起始、目標單詞如下：

N = 6
beginWord = "hit"
endWord = "cog"
wordList = ["hot", "dot", "dog", "lot", "log", "cog"]

1.?輸入數據

輸入數據：

6
hit cog
hot
dot
dog
lot
log
cog

2.?初始化

將wordList轉換為HashSet，以便快速檢查單詞是否存在。
初始化隊列queue，將beginWord加入隊列。
初始化visitMap，記錄beginWord的步數為1。

3.?廣度優先搜索（BFS）

隊列初始狀態：queue = ["hit"]，visitMap = {"hit": 1}。
循環處理隊列：
1. 取出隊列頭部單詞：curWord = "hit"，path = 1。
  - 遍歷"hit"的每個字母位置：
    - 第1個字母（h）：
      - 替換為a到z，生成新單詞：
        
        "a" + "it" = "ait"（不在wordList中，跳過）。
        
        "b" + "it" = "bit"（不在wordList中，跳過）。
        
        ...
        
        "h" + "it" = "hit"（是當前單詞，跳過）。
        
        ...
        
        "o" + "it" = "oit"（不在wordList中，跳過）。
    - 第2個字母（i）：
      - 替換為a到z，生成新單詞：
        
        "h" + "a" + "t" = "hat"（不在wordList中，跳過）。
        
        "h" + "o" + "t" = "hot"（在wordList中且未訪問過，加入隊列，記錄步數為2）。
        
        ...
    - 第3個字母（t）：
      - 替換為a到z，生成新單詞：
        
        "hi" + "a" = "hia"（不在wordList中，跳過）。
        
        ...
        
        "hi" + "g" = "hig"（不在wordList中，跳過）。
  - 隊列狀態：queue = ["hot"]，visitMap = {"hit": 1, "hot": 2}。
2. 取出隊列頭部單詞：curWord = "hot"，path = 2。
  - 遍歷"hot"的每個字母位置：
    - 第1個字母（h）：
      - 替換為a到z，生成新單詞：
        
        "a" + "ot" = "aot"（不在wordList中，跳過）。
        
        ...
        
        "d" + "ot" = "dot"（在wordList中且未訪問過，加入隊列，記錄步數為3）。
        
        ...
    - 第2個字母（o）：
      - 替換為a到z，生成新單詞：
        
        "h" + "a" + "t" = "hat"（不在wordList中，跳過）。
        
        ...
        
        "h" + "l" + "t" = "hlt"（不在wordList中，跳過）。
    - 第3個字母（t）：
      - 替換為a到z，生成新單詞：
        
        "ho" + "a" = "hoa"（不在wordList中，跳過）。
        
        ...
        
        "ho" + "g" = "hog"（不在wordList中，跳過）。
  - 隊列狀態：queue = ["dot", "lot"]，visitMap = {"hit": 1, "hot": 2, "dot": 3, "lot": 3}。
3. 取出隊列頭部單詞：curWord = "dot"，path = 3。
  - 遍歷"dot"的每個字母位置：
    - 第1個字母（d）：
      - 替換為a到z，生成新單詞：
        
        "a" + "ot" = "aot"（不在wordList中，跳過）。
        
        ...
        
        "c" + "ot" = "cot"（不在wordList中，跳過）。
    - 第2個字母（o）：
      - 替換為a到z，生成新單詞：
        
        "d" + "a" + "t" = "dat"（不在wordList中，跳過）。
        
        ...
        
        "d" + "o" + "g" = "dog"（在wordList中且未訪問過，加入隊列，記錄步數為4）。
    - 第3個字母（t）：
      - 替換為a到z，生成新單詞：
        
        "do" + "a" = "doa"（不在wordList中，跳過）。
        
        ...
        
        "do" + "g" = "dog"（已訪問過，跳過）。
  - 隊列狀態：queue = ["lot", "dog"]，visitMap = {"hit": 1, "hot": 2, "dot": 3, "lot": 3, "dog": 4}。
4. 取出隊列頭部單詞：curWord = "lot"，path = 3。
  - 遍歷"lot"的每個字母位置：
    - 第1個字母（l）：
      - 替換為a到z，生成新單詞：
        
        "a" + "ot" = "aot"（不在wordList中，跳過）。
        
        ...
        
        "c" + "ot" = "cot"（不在wordList中，跳過）。
    - 第2個字母（o）：
      - 替換為a到z，生成新單詞：
        
        "l" + "a" + "t" = "lat"（不在wordList中，跳過）。
        
        ...
        
        "l" + "o" + "g" = "log"（在wordList中且未訪問過，加入隊列，記錄步數為4）。
    - 第3個字母（t）：
      - 替換為a到z，生成新單詞：
        
        "lo" + "a" = "loa"（不在wordList中，跳過）。
        
        ...
        
        "lo" + "g" = "log"（已訪問過，跳過）。
  - 隊列狀態：queue = ["dog", "log"]，visitMap = {"hit": 1, "hot": 2, "dot": 3, "lot": 3, "dog": 4, "log": 4}。
5. 取出隊列頭部單詞：curWord = "dog"，path = 4。
  - 遍歷"dog"的每個字母位置：
    - 第1個字母（d）：
      - 替換為a到z，生成新單詞：
        
        "a" + "og" = "aog"（不在wordList中，跳過）。
        
        ...
        
        "c" + "og" = "cog"（在wordList中且未訪問過，且等于endWord，返回path + 1 = 5）。
  - 返回結果：5。

4.?輸出結果

最短轉換序列長度為5。

12.有向圖的完全可達性

卡碼網題目鏈接（ACM模式）(opens new window)

【題目描述】

給定一個有向圖，包含 N 個節點，節點編號分別為 1，2，...，N。現從 1 號節點開始，如果可以從 1 號節點的邊可以到達任何節點，則輸出 1，否則輸出 -1。

【輸入描述】

第一行包含兩個正整數，表示節點數量 N 和邊的數量 K。后續 K 行，每行兩個正整數 s 和 t，表示從 s 節點有一條邊單向連接到 t 節點。

【輸出描述】

如果可以從 1 號節點的邊可以到達任何節點，則輸出 1，否則輸出 -1。

【輸入示例】

【輸出示例】

【提示信息】

從 1 號節點可以到達任意節點，輸出 1。

數據范圍：

1 <= N <= 100；
1 <= K <= 2000。

public class Complete_Reachability_in_Directed_Graphs {public static List<List<Integer>> adjList = new ArrayList<>();//adjList 是一個存儲有向圖鄰接表的列表。外層列表的每個元素對應圖中的一個頂點，內層列表存儲從該頂點出發可以直接到達的所有頂點。例如，adjList.get(key) 返回一個列表，其中包含所有從頂點 key 出發可以直接到達的頂點。public static void dfs(boolean[] visited, int key) {//visited：一個布爾數組，用于標記每個頂點是否被訪問過。key：當前正在訪問的頂點。if (visited[key]) {//檢查頂點 key 是否已經被訪問過，如果是，則直接返回。return;}visited[key] = true;//將頂點 key 標記為已訪問（visited[key] = true）。List<Integer> nextKeys = adjList.get(key);//獲取頂點 key 的所有鄰接頂點（adjList.get(key)）。for (int nextKey : nextKeys) {//遍歷這些鄰接頂點，對每個未訪問的鄰接頂點遞歸調用 dfs 方法。dfs(visited, nextKey);}}public static void bfs(boolean[] visited, int key) {//visited：一個布爾數組，用于標記每個頂點是否被訪問過。key：當前正在訪問的頂點。Queue<Integer> queue = new LinkedList<Integer>();//創建一個隊列 queue，并將起始頂點 key 加入隊列。queue.add(key);//將起始頂點 key 標記為已訪問（visited[key] = true）。visited[key] = true;while (!queue.isEmpty()) {//當隊列不為空時，從隊列中取出一個頂點，獲取頂點 curKey 的所有鄰接頂點（adjList.get(curKey)）。遍歷這些鄰接頂點，對每個未訪問的鄰接頂點，將其加入隊列并標記為已訪問。int curKey = queue.poll();List<Integer> list = adjList.get(curKey);for (int nextKey : list) {if (!visited[nextKey]) {queue.add(nextKey);visited[nextKey] = true;}}}}public static void main(String[] args) {Scanner sc = new Scanner(System.in);//使用Scanner類從標準輸入讀取數據。首先讀取兩個整數vertices_num和line_num，分別代表圖中頂點的數量和邊的數量。初始化鄰接表adjList，為每個頂點創建一個空列表。int vertices_num = sc.nextInt();int line_num = sc.nextInt();for (int i = 0; i < vertices_num; i++) {adjList.add(new LinkedList<>());}for (int i = 0; i < line_num; i++) {//循環讀取 line_num 條邊的信息，每條邊由起點 s 和終點 t 表示。注意，代碼中頂點編號從 0 開始，而輸入可能從 1 開始，所以使用 s - 1 和 t - 1 將頂點編號轉換為從 0 開始。將每條邊的終點添加到起點的鄰接列表中。int s = sc.nextInt();int t = sc.nextInt();adjList.get(s - 1).add(t - 1);}boolean[] visited = new boolean[vertices_num];//創建一個布爾數組 visited，用于跟蹤每個頂點的訪問狀態。從頂點 0 開始執行 DFS 遍歷。dfs(visited, 0);for (int i = 0; i < vertices_num; i++) {//遍歷 visited 數組，如果存在未訪問的頂點，則輸出 -1 并結束程序，表示不是所有頂點都可達。如果所有頂點都被訪問過，則輸出 1，表示從起始頂點 0 到其他所有頂點都是完全可達的。if (!visited[i]) {System.out.println(-1);return;}}System.out.println(1);}
}

假設輸入的圖如下：

頂點數：4
邊數：4
邊信息：
1 2
1 3
2 4
3 4

對應的有向圖如下：

1 -> 2 -> 4\    /\-> 3

1.?輸入數據

輸入數據：

2.?初始化鄰接表

鄰接表adjList初始化為：

adjList[0] = [1, 2] // 頂點0（輸入中的1）可以到達頂點1（輸入中的2）和頂點2（輸入中的3）
adjList[1] = [3]    // 頂點1（輸入中的2）可以到達頂點3（輸入中的4）
adjList[2] = [3]    // 頂點2（輸入中的3）可以到達頂點3（輸入中的4）
adjList[3] = []     // 頂點3（輸入中的4）沒有出邊

3.?執行DFS

從頂點0開始執行DFS：

訪問頂點0：
- 標記visited[0] = true。
- 鄰接頂點為1和2，遞歸訪問頂點1和2。
訪問頂點1：
- 標記visited[1] = true。
- 鄰接頂點為3，遞歸訪問頂點3。
訪問頂點2：
- 標記visited[2] = true。
- 鄰接頂點為3，遞歸訪問頂點3。
訪問頂點3：
- 標記visited[3] = true。
- 頂點3沒有鄰接頂點，遞歸返回。

4.?檢查訪問狀態

遍歷visited數組：

visited = [true, true, true, true]

所有頂點都被訪問過，因此輸出1。

13.島嶼的周長

卡碼網題目鏈接（ACM模式）(opens new window)

題目描述

給定一個由 1（陸地）和 0（水）組成的矩陣，島嶼是被水包圍，并且通過水平方向或垂直方向上相鄰的陸地連接而成的。

你可以假設矩陣外均被水包圍。在矩陣中恰好擁有一個島嶼，假設組成島嶼的陸地邊長都為 1，請計算島嶼的周長。島嶼內部沒有水域。

輸入描述

第一行包含兩個整數 N, M，表示矩陣的行數和列數。之后 N 行，每行包含 M 個數字，數字為 1 或者 0，表示島嶼的單元格。

輸出描述

輸出一個整數，表示島嶼的周長。

輸入示例

輸出示例

提示信息

島嶼的周長為 14。

數據范圍：

1 <= M, N <= 50。

public class Island_Perimeter {static int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};//二維數組，定義了四個方向的移動，分別對應下（{1, 0}）、上（{-1, 0}）、右（{0, 1}）、左（{0, -1}）。在后續計算陸地單元格周長時，通過這個數組可以方便地獲取當前單元格的四個相鄰單元格的坐標。static int count;//靜態變量，用于臨時存儲單個陸地單元格的周長。public static void helper(int[][] grid, int x, int y) {//輔助方法，用于計算單個島嶼單元格的周長。int[][] grid 是輸入的二維數組，表示地圖。int x 和 int y 是當前島嶼單元格的坐標。for (int[] dir : dirs) {//使用 for 循環遍歷 dirs 數組，計算當前陸地單元格在四個方向上相鄰單元格的坐標 (nx, ny)。int nx = x + dir[0];int ny = y + dir[1];if (nx < 0 || nx >= grid.length || ny < 0 || ny >= grid[0].length//如果相鄰單元格的坐標越界（即 nx < 0 或 nx >= grid.length 或 ny < 0 或 ny >= grid[0].length），說明該方向上是地圖邊界，當前陸地單元格在這個方向上有一條邊貢獻給周長，count 加 1。|| grid[nx][ny] == 0) {//如果相鄰單元格的值為 0，表示該方向上是水域，當前陸地單元格在這個方向上有一條邊貢獻給周長，count 加 1。count++;}}}public static void main(String[] args) {Scanner sc = new Scanner(System.in);//使用Scanner類從標準輸入讀取數據。首先讀取兩個整數M和N，分別代表地圖的行數和列數。創建一個大小為M x N的二維數組grid，用于存儲地圖數據。循環讀取M x N個整數填充grid。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();}}int result = 0;//初始化result為0，用于存儲所有島嶼的周長總和。遍歷整個地圖，對于每個值為1的單元格（即島嶼的一部分），重置count為0，然后調用helper方法計算該單元格的周長，并將其累加到result中。for (int i = 0; i < M; i++) {for (int j = 0; j < N; j++) {if (grid[i][j] == 1) {count = 0;helper(grid, i, j);result += count;}}}System.out.println(result);//最后，將計算得到的所有島嶼的總周長 result 輸出到標準輸出。}
}

假設輸入的地圖如下：

1.?輸入數據

輸入數據：

2.?初始化

創建一個二維數組grid，并填充輸入數據。

3.?計算每個陸地單元格的周長

遍歷地圖：從左到右、從上到下遍歷每個單元格。
遇到陸地單元格（值為1）：
- 調用helper方法，計算當前陸地單元格的周長。
- 將計算結果累加到result中。

4.?`helper`方法的執行

對于每個陸地單元格，檢查其四個方向的相鄰單元格：
- 如果相鄰單元格越界或為水域（值為0），則當前方向上有一條邊貢獻給周長，count加1。
示例中的計算：
- 單元格(0,0)：
  - 下：(1,0)是陸地，不貢獻周長。
  - 上：越界，貢獻1。
  - 右：(0,1)是水域，貢獻1。
  - 左：越界，貢獻1。
  - 總周長：count = 3。
- 單元格(1,0)：
  - 下：(2,0)是水域，貢獻1。
  - 上：(0,0)是陸地，不貢獻周長。
  - 右：(1,1)是陸地，不貢獻周長。
  - 左：越界，貢獻1。
  - 總周長：count = 2。
- 單元格(1,1)：
  - 下：(2,1)是陸地，不貢獻周長。
  - 上：(0,1)是水域，貢獻1。
  - 右：(1,2)是水域，貢獻1。
  - 左：(1,0)是陸地，不貢獻周長。
  - 總周長：count = 2。
- 單元格(2,1)：
  - 下：(3,1)是水域，貢獻1。
  - 上：(1,1)是陸地，不貢獻周長。
  - 右：(2,2)是水域，貢獻1。
  - 左：越界，貢獻1。
  - 總周長：count = 3。
- 單元格(3,2)：
  - 下：越界，貢獻1。
  - 上：(2,2)是水域，貢獻1。
  - 右：(3,3)是陸地，不貢獻周長。
  - 左：(3,1)是水域，貢獻1。
  - 總周長：count = 3。
- 單元格(3,3)：
  - 下：越界，貢獻1。
  - 上：(2,3)越界，貢獻1。
  - 右：越界，貢獻1。
  - 左：(3,2)是陸地，不貢獻周長。
  - 總周長：count = 3。