返回目录

题目描述

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

输出描述

输出小华最多能获得多少克黄金

示例：

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

题目解析

本题题目描述有些歧义

在横坐标和纵坐标的数位之和不大于 k 的方格中存在黄金（每个方格中仅存在一克黄金）

和

但横坐标和纵坐标之和大于 k 的方格存在危险不可进入

这两句话有点矛盾，所谓横坐标和纵坐标的数位之和，比如：

  • 横坐标是10，那么横坐标的数位和 = 1 + 0 = 1
  • 纵坐标是21，那么纵坐标的数位和 = 2 + 1 = 3
  • 横坐标和纵坐标的数位之和 = 1 + 3 = 4

但是横坐标和纵坐标之和

  • 横坐标是10，纵坐标是21，横坐标和纵坐标之和 = 10 + 21 = 31

Python算法源码

import sys

class GoldMine:
    def __init__(self, m, n, k):
        """
        初始化金矿类对象。

        参数:
            m (int): 金矿行数。
            n (int): 金矿列数。
            k (int): 数位和的限制。
        """
        self.m = m
        self.n = n
        self.k = k
        self.ans = 0
        self.visited = set()
        self.offsets = ((-1, 0), (1, 0), (0, -1), (0, 1))
        self.digitSums = [0] * max(m, n)
        for i in range(len(self.digitSums)):
            num = i
            while num > 0:
                self.digitSums[i] += num % 10
                num //= 10

    def dfs(self, x, y):
        """
        深度优先搜索金矿。

        参数:
            x (int): 当前位置的行坐标。
            y (int): 当前位置的列坐标。
        """
        if x < 0 or x >= self.m or y < 0 or y >= self.n:
            return
        if self.digitSums[x] + self.digitSums[y] > self.k:
            return
        pos = x * self.n + y
        if pos in self.visited:
            return
        self.visited.add(pos)
        self.ans += 1
        for offsetX, offsetY in self.offsets:
            newX = x + offsetX
            newY = y + offsetY
            self.dfs(newX, newY)

    def find_gold(self):
        """
        寻找金矿的入口函数。
      
        返回:
            int: 可采集的金矿数量。
        """
        self.dfs(0, 0)
        return self.ans

# 输入获取
m, n, k = map(int, input().split())

# 算法入口
gold_mine = GoldMine(m, n, k)
print(gold_mine.find_gold())

C算法源码


#include <stdio.h>

// 全局变量
int ans = 0; // 记录结果
int visited[5000]; // 记录已访问的位置，避免重复计算
int offsets[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 上下左右偏移量
int digitSums[5000]; // 数位和数组

// 深度优先搜索函数
void dfs(int x, int y, int m, int n, int k) {
    // 如果位置越界，则返回
    if (x < 0 || x >= m || y < 0 || y >= n)
        return;

    // 如果横坐标和纵坐标对应的数位和之和超过k，则返回
    if (digitSums[x] + digitSums[y] > k)
        return;

    int pos = x * n + y;

    // 如果位置已经访问过，则返回
    if (visited[pos])
        return;

    // 将位置标记为已访问
    visited[pos] = 1;

    // 增加结果计数
    ans++;

    // 继续在上下左右四个方向进行深度优先搜索
    for (int i = 0; i < 4; i++) {
        int newX = x + offsets[i][0];
        int newY = y + offsets[i][1];
        dfs(newX, newY, m, n, k);
    }
}

int main() {
    // 输入
    int m, n, k;
    scanf("%d %d %d", &m, &n, &k);

    // 初始化数位和数组
    for (int i = 0; i < (m > n ? m : n); i++) {
        int num = i;
        while (num > 0) {
            digitSums[i] += num % 10;
            num /= 10;
        }
    }

    // 执行深度优先搜索
    dfs(0, 0, m, n, k);

    // 输出结果
    printf("%d\n", ans);

    return 0;
}

Java算法源码

import java.util.Scanner;

public class Main {
    // 记录题解
    static int ans = 0;
    // 记录已访问过的位置，避免重复统计
    static int[] visited;
    // 上下左右偏移量
    static int[][] offsets = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    // 数位和数组
    static int[] digitSums;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt();
        int n = scanner.nextInt();
        int k = scanner.nextInt();

        // digitSums数组的索引是原始数，值是原始数对应的数位和
        int maxSize = Math.max(m, n);
        digitSums = new int[maxSize];
        for (int i = 0; i < maxSize; i++) {
            int num = i;
            while (num > 0) {
                digitSums[i] += num % 10;
                num /= 10;
            }
        }

        // visited数组记录已访问过的位置，避免重复统计
        visited = new int[m * n];

        dfs(0, 0, m, n, k);
        System.out.println(ans);
    }

    static void dfs(int x, int y, int m, int n, int k) {
        // 如果对应位置越界，则不能进入
        if (x < 0 || x >= m || y < 0 || y >= n) {
            return;
        }

        // 如果对应位置已横坐标、纵坐标的数位和之和超过了k，则不能进入
        if (digitSums[x] + digitSums[y] > k) {
            return;
        }

        // 如果对应位置已访问过，则不能进入
        int pos = x * n + y;
        if (visited[pos] == 1) {
            return;
        }

        // 否则可以进入
        visited[pos] = 1;
        // 且获得黄金
        ans += 1;

        // 继续遍历上、下、左、右方向上的新位置继续深搜
        for (int i = 0; i < 4; i++) {
            int newX = x + offsets[i][0];
            int newY = y + offsets[i][1];
            dfs(newX, newY, m, n, k);
        }
    }
}
最后修改：2024 年 03 月 31 日
© 允许规范转载
如果觉得我的文章对你有用，请随意赞赏