算法思想之深度优先搜索（DFS）、递归以及案例（最多能得到多少克黄金、精准核酸检测、最富裕的小家庭）

深度优先搜索（DFS）、递归

• 深度优先搜索（Depth First Search，DFS）是一种用于遍历或搜索树或图的算法。在 DFS 算法中，从起始节点开始，沿着一条路径尽可能深地访问节点，直到到达叶子节点或者无法继续前进为止。然后退回到最近的一个有未探索节点的分支节点，继续探索其他路径，直到所有节点都被访问过为止。
• 深度优先搜索常常用于解决以下类型的问题：深度优先搜索是一种简单而强大的算法，可以解决许多实际问题。
  • 图遍历：在无向图或有向图中寻找特定节点之间的路径、判断图的连通性等。
  • 连通性问题：判断图中是否存在环、判断图的强连通分量等。
  • 组合问题：生成排列、组合或子集等组合型问题。
  • 寻路问题：求解从起始点到目标点的最短路径或所有可行路径。
  • 递归问题：通过递归实现深度优先搜索，例如二叉树的遍历等。

小华最多能得到多少克黄金

• 题目描述小华按照地图去寻宝，地图上被划分成 m 行和 n 列的方格，横纵坐标范围分别是 [0, n-1] 和 [0, m-1]。在横坐标和纵坐标的数位之和不大于 k 的方格中存在黄金（每个方格中仅存在一克黄金），但横坐标和纵坐标之和大于 k 的方格存在危险不可进入。小华从入口 (0,0) 进入，任何时候只能向左，右，上，下四个方向移动一格。请问小华最多能获得多少克黄金？输入要求坐标取值范围如下：k 的取值范围如下：输入中包含3个字数，分别是m, n, k输出要求输出小华最多能获得多少克黄金
  • 0 ≤ m ≤ 50
  • 0 ≤ n ≤ 50
• 0 ≤ k ≤ 100
• 例如，对于数字1234，它的各个位上的数字分别是1、2、3和4，那么它的数位之和就等于1+2+3+4=10。同样地，对于数字56789，它的数位之和就等于5+6+7+8+9=35。
• 在题目中，提到横纵坐标的数位之和不大于k，意味着将横坐标和纵坐标的每个位上的数字相加，得到的和要小于或等于k。
• 首先，可以定义一个函数 dfs 来进行深度优先搜索。这个函数可以接受当前位置的坐标 (x, y)、当前黄金数量 gold 和已经访问过的方格集合 visited 作为参数。
• 在 dfs 函数中，首先判断当前位置是否越界或者已经访问过，如果是则直接返回。然后判断当前位置的横纵坐标的数位之和是否大于 k，如果是则说明是危险方格，也直接返回。否则，将当前位置标记为已访问，并将当前位置的黄金数量加上当前方格的黄金数量。
• 接下来，递归地调用 dfs 函数来搜索当前位置的上、下、左、右四个方向的相邻方格。对于每个相邻方格，传入更新后的坐标和黄金数量，并将得到的结果取最大值。
• 最后，在主函数中，从入口位置 (0, 0) 开始调用 dfs 函数，并输出返回的最大黄金数量。

题解数位之和是指一个数的各个位上数字的和。这道题可以使用深度优先搜索（DFS）算法来解决。

importjava.util.*;publicclassMain{staticint m, n, k;staticint[] xArr ={-1,1,0,0}, yArr ={0,0,1,-1};publicstaticvoidmain(String[] args){Scanner sc =newScanner(System.in);while(sc.hasNext()){ m = sc.nextInt(); n = sc.nextInt(); k = sc.nextInt();System.out.println(move(0,0,0,newHashSet<>()));}}publicstaticintmove(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;}publicstaticintcalculate(int n){int ret =0;while(n %10>0){ ret += n %10; n /=10;}return ret;}}

用例1

输入： 40 40 18 输出：1484 

用例2

输入： 5 4 7 输出：20 

精准核酸检测

• 题目描述为了达到新冠疫情精准防控的需要，为了避免全员核酸检测带来的浪费，需要精准圈定可能被感染的人群。现在根据传染病流调以及大数据分析，得到了每个人之间在时间、空间上是否存在轨迹交叉。现在给定一组确诊人员编号（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

题解

importjava.util.*;publicclassMain{publicstaticvoidmain(String[] args){Scanner sc =newScanner(System.in);while(sc.hasNext()){int n =Integer.parseInt(sc.nextLine());int[] arr =Arrays.stream(sc.nextLine().split(",")).mapToInt(Integer::parseInt).toArray();int[][] arrs =newint[n][n];for(int i =0; i < n; i++) arrs[i]=Arrays.stream(sc.nextLine().split(",")).mapToInt(Integer::parseInt).toArray();HashSet<Integer> set =newHashSet<>();// 存储确诊和需要检测的人for(int i : arr){ set.add(i);reDo(i, arrs, set);}System.out.println(set.size()- arr.length);// 减去确诊人数}}publicstaticvoidreDo(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);}}}}

用例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人需要核酸检测 

最富裕的小家庭

• 题目描述在一颗树中，每个节点代表一个家庭成员，节点的数字表示其个人的财富值，一个节点及其直接相连的子节点被定义为一个小家庭。现给你一颗树，请计算出最富裕的小家庭的财富和。输入要求第一行为一个数 N，表示成员总数，成员编号 1~N。1 ≤ N ≤ 1000第二行为 N 个空格分隔的数，表示编号 1~N 的成员的财富值。0 ≤ 财富值 ≤ 1000000接下来 N -1 行，每行两个空格分隔的整数（N1, N2），表示 N1 是 N2 的父节点。输出要求最富裕的小家庭的财富和

题解

importjava.util.*;publicclassMain{-l publicstaticvoidmain(String[] args){Scanner sc =newScanner(System.in);while(sc.hasNext()){int n = sc.nextInt();int[] arr =newint[n +1];// 数组索引从0开始，成员编号从1开始，故n个成员需要n+1大小数组for(int i =0; i < n; i++)// 成员编号从1开始，以成员编号作为数组索引 arr[i +1]= sc.nextInt();List<List<Integer>> list =newArrayList<>();for(int i =0; i <= n; i++)// 集合add从索引0开始，从索引1开始与成员编号对齐 list.add(newArrayList<>());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);}}}

用例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