深度優先搜索（DFS）、遞歸

• 深度優先搜索（Depth First Search，DFS）是一種用于遍歷或搜索樹或圖的算法。在 DFS 算法中，從起始節點開始，沿著一條路徑盡可能深地訪問節點，直到到達葉子節點或者無法繼續前進為止。然后退回到最近的一個有未探索節點的分支節點，繼續探索其他路徑，直到所有節點都被訪問過為止。

• 深度優先搜索常常用于解決以下類型的問題：

  • 圖遍歷：在無向圖或有向圖中尋找特定節點之間的路徑、判斷圖的連通性等。
  • 連通性問題：判斷圖中是否存在環、判斷圖的強連通分量等。
  • 組合問題：生成排列、組合或子集等組合型問題。
  • 尋路問題：求解從起始點到目標點的最短路徑或所有可行路徑。
  • 遞歸問題：通過遞歸實現深度優先搜索，例如二叉樹的遍歷等。

  深度優先搜索是一種簡單而強大的算法，可以解決許多實際問題。

小華最多能得到多少克黃金

• 題目描述

  小華按照地圖去尋寶，地圖上被劃分成 m 行和 n 列的方格，橫縱坐標范圍分別是 [0, n-1] 和 [0, m-1]。

  在橫坐標和縱坐標的數位之和不大于 k 的方格中存在黃金（每個方格中僅存在一克黃金），但橫坐標和縱坐標之和大于 k 的方格存在危險不可進入。小華從入口 (0,0) 進入，任何時候只能向左，右，上，下四個方向移動一格。

  請問小華最多能獲得多少克黃金？

  輸入要求

  坐標取值范圍如下：

  • 0 ≤ m ≤ 50
  • 0 ≤ n ≤ 50

  k 的取值范圍如下：

  • 0 ≤ k ≤ 100

  輸入中包含3個字數，分別是m, n, k

  輸出要求

  輸出小華最多能獲得多少克黃金

• 用例1

  輸入：
  40 40 18
  輸出：1484
  

  用例2

  輸入：
  5 4 7
  輸出：20
  

• 題解

  數位之和是指一個數的各個位上數字的和。

  • 例如，對于數字1234，它的各個位上的數字分別是1、2、3和4，那么它的數位之和就等于1+2+3+4=10。

    同樣地，對于數字56789，它的數位之和就等于5+6+7+8+9=35。

  • 在題目中，提到橫縱坐標的數位之和不大于k，意味著將橫坐標和縱坐標的每個位上的數字相加，得到的和要小于或等于k。

  這道題可以使用深度優先搜索（DFS）算法來解決。

  1. 首先，可以定義一個函數 dfs 來進行深度優先搜索。這個函數可以接受當前位置的坐標 (x, y)、當前黃金數量 gold 和已經訪問過的方格集合 visited 作為參數。
  2. 在 dfs 函數中，首先判斷當前位置是否越界或者已經訪問過，如果是則直接返回。然后判斷當前位置的橫縱坐標的數位之和是否大于 k，如果是則說明是危險方格，也直接返回。否則，將當前位置標記為已訪問，并將當前位置的黃金數量加上當前方格的黃金數量。
  3. 接下來，遞歸地調用 dfs 函數來搜索當前位置的上、下、左、右四個方向的相鄰方格。對于每個相鄰方格，傳入更新后的坐標和黃金數量，并將得到的結果取最大值。
  4. 最后，在主函數中，從入口位置 (0, 0) 開始調用 dfs 函數，并輸出返回的最大黃金數量。

  import java.util.*;
  public class Main {static int m, n, k;static int[] xArr = {-1, 1, 0, 0}, yArr = {0, 0, 1, -1};public static void main(String[] args) {Scanner sc = new Scanner(System.in);while (sc.hasNext()) {m = sc.nextInt(); n = sc.nextInt(); k = sc.nextInt();System.out.println(move(0, 0, 0, new HashSet<>()));}}public static int move(int x, int y, int ret, Set<String> visited) {if (x < 0 || x > n - 1 || y < 0 || y > m -1 || visited.contains(x + "," + y)|| calculate(x) + calculate(y) > k)return ret;ret++;visited.add(x + "," + y);for (int i = 0; i < 4; i++)ret = Math.max(ret, move(x + xArr[i], y + yArr[i], ret, visited));return ret;}public static int calculate(int n) {int ret = 0;while (n % 10 > 0) {ret += n % 10;n /= 10;}return ret;}
  }
  

精準核酸檢測

• 題目描述

  為了達到新冠疫情精準防控的需要，為了避免全員核酸檢測帶來的浪費，需要精準圈定可能被感染的人群。

  現在根據傳染病流調以及大數據分析，得到了每個人之間在時間、空間上是否存在軌跡交叉。

  現在給定一組確診人員編號（X1, X2, X3,…, Xn），在所有人當中，找出哪些人需要進行核酸檢測，輸出需要進行核酸檢測的人數。（注意：確診病例自身不需要再做核酸檢測）

  需要進行核酸檢測的人，是病毒傳播鏈條上的所有人員，即有可能通過確診病例所能傳播到的所有人。

  例如：A 是確診病例，A 和 B 有接觸、B 和 C 有接觸、C 和 D 有接觸、D 和 E 有接觸，那么 B、C、D、E 都是需要進行核酸檢測的人。

  輸入要求

  第一行為總人數 N

  第二行為確認病例人員編號（確診病例人員數量 < N），用逗號分割

  第三行開始，為一個 N * N 的矩陣，表示每個人員之間是否有接觸，0 表示沒有接觸，1 表示有接觸。

  輸出要求

  整數：需要做核酸檢測的人數

  特別說明

  • 人員編號從 0 開始
  • 0 < N < 100

• 用例1

  輸入：
  5
  1,2
  1,1,0,1,0
  1,1,0,0,0
  0,0,1,0,1
  1,0,0,1,0
  0,0,1,0,1
  輸出：3
  說明：
  編號為1、2號的人員，為確診病例。
  1號與0號有接觸，0號與3號有接觸
  2號與4號有接觸
  故0、3、4號共3人需要核酸檢測
  

• 題解

  import java.util.*;
  public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);while (sc.hasNext()) {int n = Integer.parseInt(sc.nextLine());int[] arr = Arrays.stream(sc.nextLine().split(",")).mapToInt(Integer::parseInt).toArray();int[][] arrs = new int[n][n];for (int i = 0; i < n; i++)arrs[i] = Arrays.stream(sc.nextLine().split(",")).mapToInt(Integer::parseInt).toArray();HashSet<Integer> set = new HashSet<>(); // 存儲確診和需要檢測的人for (int i : arr) {set.add(i);reDo(i, arrs, set);}System.out.println(set.size() - arr.length); // 減去確診人數}}public static void reDo(int i, int[][] arrs, HashSet<Integer> set) {for (int j = 0; j < arrs[i].length; j++) {if (arrs[i][j] == 1 && !set.contains(j)){ // 遞歸終止條件set.add(j);reDo(j, arrs, set);}}}
  }
  

最富裕的小家庭

• 題目描述

  在一顆樹中，每個節點代表一個家庭成員，節點的數字表示其個人的財富值，一個節點及其直接相連的子節點被定義為一個小家庭。

  現給你一顆樹，請計算出最富裕的小家庭的財富和。

  輸入要求

  第一行為一個數 N，表示成員總數，成員編號 1~N。1 ≤ N ≤ 1000

  第二行為 N 個空格分隔的數，表示編號 1~N 的成員的財富值。0 ≤ 財富值 ≤ 1000000

  接下來 N -1 行，每行兩個空格分隔的整數（N1, N2），表示 N1 是 N2 的父節點。

  輸出要求

  最富裕的小家庭的財富和

• 用例1

  輸入：
  4
  100 200 300 500
  1 2
  1 3
  2 4
  輸出：700
  說明：成員1，2，3 組成的小家庭財富值為600，成員2，4 組成的小家庭財富值為700
  

  用例2

  輸入：
  4
  100 200 300 500
  1 2
  1 3
  1 4
  輸出：1100
  說明：成員1，2，3 組成的小家庭財富值為600，成員2，4 組成的小家庭財富值為700
  

• 題解

  import java.util.*;
  public class Main {-lpublic static void main(String[] args) {Scanner sc = new Scanner(System.in);while (sc.hasNext()) {int n = sc.nextInt();int[] arr = new int[n + 1]; // 數組索引從0開始，成員編號從1開始，故n個成員需要n+1大小數組for (int i = 0; i < n; i++) // 成員編號從1開始，以成員編號作為數組索引arr[i + 1] = sc.nextInt();List<List<Integer>> list = new ArrayList<>();for (int i = 0; i <= n; i++) // 集合add從索引0開始，從索引1開始與成員編號對齊list.add(new ArrayList<>());for (int i = 0; i < n - 1; i++)list.get(sc.nextInt()).add(sc.nextInt());int max = 0;for (int i = 1; i <= n; i++) {int sum = arr[i];for (Integer sun : list.get(i)) // 遍歷該成員編號的所有直接連接的子節點sum += arr[sun];max = Math.max(max, sum);}System.out.println(max);}}
  }