深度优先搜索（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 函数，并输出返回的最大黄金数量。
题解
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) {
(System.in);
(sc.hasNext()) {
m = sc.nextInt();
n = sc.nextInt();
k = sc.nextInt();
System.out.println(move(, , , <>()));
}
}
{
(x < || x > n - || y < || y > m - || visited.contains(x + + y) || calculate(x) + calculate(y) > k)
ret;
ret++;
visited.add(x + + y);
( ; i < ; i++)
ret = Math.max(ret, move(x + xArr[i], y + yArr[i], ret, visited));
ret;
}
{
;
(n > ) {
ret += n % ;
n /= ;
}
ret;
}
}
