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

题目描述

小华按照地图去寻宝，地图上被划分成 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

输入：
4 5 7

输出：
20

说明：
如图每个单元格中的数位之和不大于 
7
7，都是符合要求的，所以可以最多可获得 
20
20 克黄金

题解

这道题目是一个搜索问题，需要从入口 (0, 0) 开始，使用深度优先搜索（DFS）来遍历满足数位之和条件的方格。在搜索的过程中，需要判断坐标的有效性和数位之和是否满足条件。同时，使用一个二维数组 vis 来记录已经访问过的方格，避免重复访问。

具体步骤如下：

1. 定义一个函数 sum_of_digits 用于计算一个数字的数位之和。
2. 定义 DFS 函数，接收当前坐标 (r, c)，在函数中进行如下判断：
   • 验证坐标有效性：r 和 c 不越界，且当前方格未被访问。
   • 计算数位之和，如果数位之和大于 k，则不再递归下去。
3. 在 DFS 函数中标记当前方格为已访问，并增加黄金数量。
4. 递归调用 DFS 函数，分别向上、向下、向左、向右四个方向进行搜索。
5. 主函数中读入 m、n、k 的值，初始化 gold 为 0，并创建一个二维数组 vis 用于记录访问状态。
6. 调用 DFS 函数开始搜索，从入口 (0, 0) 开始。
7. 输出最终的黄金数量。

复杂度分析

时间复杂度：在最坏情况下，每个方格可能都需要访问一次，因此时间复杂度为 O(m * n)。

空间复杂度：使用了一个二维数组 vis 来记录访问状态，因此空间复杂度为 O(m * n)。同时，递归调用的栈空间也需要考虑，但在这里由于递归深度不会很大，可以近似为 O(1)。

C++

#include <bits/stdc++.h>
using namespace std;

int  gold;
int  m, n, k;
bool vis[55][55];

// 求数位之和
int sum_of_digits(int num)
{
    int sum = 0;
    while (num) {
        sum += num % 10;
        num /= 10;
    }
    return sum;
}

void dfs(int r, int c)
{
    // 验证坐标有效性
    if (r < 0 || c < 0 || r >= m || c >= n || vis[r][c]) return;

    // 求数位之和，如果数位之和大于k，则不再递归下去了
    if (sum_of_digits(r) + sum_of_digits(c) > k) return;
    vis[r][c] = true;
    gold++;

    // 递归调用
    dfs(r - 1, c);
    dfs(r + 1, c);
    dfs(r, c - 1);
    dfs(r, c + 1);
}

int main()
{
    cin >> m >> n >> k;

    // 初始化
    gold = 0;
    memset(vis, 0, sizeof(vis));

    dfs(0, 0);

    cout << gold << endl;

    return 0;
}
    

🙏整理题解不易， 如果有帮助到您，请给点个赞 ‍❤️‍ 和收藏 ⭐，让更多的人看到。🙏🙏🙏