深度优先搜索（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）算法来解决。
- 首先，可以定义一个函数 dfs 来进行深度优先搜索。这个函数可以接受当前位置的坐标 (x, y)、当前黄金数量 gold 和已经访问过的方格集合 visited 作为参数。
- 在 dfs 函数中，首先判断当前位置是否越界或者已经访问过，如果是则直接返回。然后判断当前位置的横纵坐标的数位之和是否大于 k，如果是则说明是危险方格，也直接返回。否则，将当前位置标记为已访问，并将当前位置的黄金数量加上当前方格的黄金数量。
- 接下来，递归地调用 dfs 函数来搜索当前位置的上、下、左、右四个方向的相邻方格。对于每个相邻方格，传入更新后的坐标和黄金数量，并将得到的结果取最大值。
- 最后，在主函数中，从入口位置 (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 {-l public 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); } } }