机考E卷200分题 - 周末爬山

题目描述

周末小明准备去爬山锻炼，0代表平地，山的高度使用1到9来表示，小明每次爬山或下山高度只能相差k及k以内，每次只能上下左右一个方向上移动一格，小明从左上角(0,0)位置出发

输入描述

第一行输入m n k(空格分隔)

  • 代表m*n的二维山地图，k为小明每次爬山或下山高度差的最大值，

然后接下来输入山地图，一共m行n列，均以空格分隔。取值范围：

  • 0 < m ≤ 500
  • 0< n ≤ 500
  • 0 < k < 5

备注

所有用例输入均为正确格式，且在取值范围内，考生不需要考虑不合法的输入格式。

输出描述

请问小明能爬到的最高峰多高，到该最高峰的最短步数，输出以空格分隔。

同高度的山峰输出较短步数。

如果没有可以爬的山峰，则高度和步数都返回0。

示例1

输入

5 4 1
0 1 2 0
1 0 0 0
1 0 1 2
1 3 1 0
0 0 0 9
123456

输出

2 2
1

说明

根据山地图可知，能爬到的最高峰在(0,2)位置，高度为2，最短路径为(0,0)-(0,1)-(0,2)，最短步数为2。

示例2

输入

5 4 3
0 0 0 0
0 0 0 0
0 9 0 0
0 0 0 0
0 0 0 9
123456

输出

0 0
1

说明

根据山地图可知，每次爬山距离3，无法爬到山峰上，步数为0。

解题思路

这个问题的解题思路是使用深度优先搜索（DFS）算法来解决小明爬山的问题。

  1. 定义一个常量数组 OFFSETS，表示上下左右四个方向的偏移量。这将帮助我们在搜索过程中遍历相邻的位置。

  2. 实现一个深度优先搜索函数 dfs，它接收以下参数：当前位置的坐标 (x, y)，当前步数 step，一个哈希表 min_step_to_height 用于存储到达不同高度的最短步数，山地图矩阵 matrix，矩阵的行数 m 和列数 n，允许的最大高度差 k，一个记忆化数组 memo 用于记录已经访问过的位置和步数，以及一个布尔数组 visited 用于记录已经访问过的位置。

  3. 在 dfs 函数中，首先获取当前位置的高度。

  4. 遍历四个方向（上下左右），计算新的位置，并检查新位置是否在矩阵范围内。

  5. 获取新位置的高度，并检查两个位置的高度差是否在 k 以内。如果高度差在 k 以内，执行以下操作：

    a. 增加步数。

    b. 更新到达新高度的最短步数。如果当前高度不在 min_step_to_height 中，或者当前步数小于已记录的最短步数，更新 min_step_to_height。

    c. 检查记忆化数组，避免重复计算。如果当前位置没有被访问过，或者已访问过但当前步数小于已记录的步数，执行以下操作：

    i. 更新记忆化数组。

    ii. 标记当前位置为已访问。

    iii. 递归调用 dfs 函数，继续搜索。

    iv. 回溯时，将当前位置标记为未访问。

    d. 减少步数。

Java

import java.util.HashMap;
import java.util.Scanner;

public class Main {
    // 定义一个常量数组，表示上下左右四个方向的偏移量
    private static final int[][] OFFSETS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 读取输入的m, n, k
        int m = sc.nextInt();
        int n = sc.nextInt();
        int k = sc.nextInt();

        // 初始化山地图矩阵
        int[][] matrix = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                matrix[i][j] = sc.nextInt();
            }
        }

        // 初始化一个哈希表，用于存储到达不同高度的最短步数
        HashMap<Integer, Integer> minStepToHeight = new HashMap<>();
        minStepToHeight.put(matrix[0][0], 0);

        // 初始化一个记忆化数组，用于记录已经访问过的位置和步数
        int[][] memo = new int[m][n];
        // 初始化一个布尔数组，用于记录已经访问过的位置
        boolean[][] visited = new boolean[m][n];
        // 调用深度优先搜索函数
        dfs(0, 0, 0, minStepToHeight, matrix, m, n, k, memo, visited);

        // 计算最高峰的高度和最短步数
        int maxHeight = minStepToHeight.keySet().stream().max((a, b) -> a - b).orElse(0);
        int minStep = minStepToHeight.get(maxHeight);

        // 输出结果
        System.out.println(maxHeight + " " + minStep);
    }

    // 深度优先搜索函数
    public static void dfs(int x, int y, int step, HashMap<Integer, Integer> minStepToHeight, int[][] matrix, int m, int n, int k, int[][] memo, boolean[][] visited) {
        // 获取当前位置的高度
        int lastHeight = matrix[x][y];

        // 遍历四个方向
        for (int[] offset : OFFSETS) {
            // 计算新的位置
            int newX = x + offset[0];
            int newY = y + offset[1];

            // 检查新位置是否在矩阵范围内
            if (newX < 0 || newX >= m || newY < 0 || newY >= n) continue;

            // 获取新位置的高度
            int curHeight = matrix[newX][newY];

            // 检查两个位置的高度差是否在k以内
            if (Math.abs(curHeight - lastHeight) <= k) {
                // 增加步数
                step++;

                // 更新到达新高度的最短步数
                if (!minStepToHeight.containsKey(curHeight) || minStepToHeight.get(curHeight) > step) {
                    minStepToHeight.put(curHeight, step);
                }

                // 检查记忆化数组，避免重复计算
                if (memo[newX][newY] == 0 || memo[newX][newY] > step) {
                    // 更新记忆化数组
                    memo[newX][newY] = step;
                    // 标记当前位置为已访问
                    visited[x][y] = true;

                    // 递归调用深度优先搜索
                    dfs(newX, newY, step, minStepToHeight, matrix, m, n, k, memo, visited);

                    // 回溯时，将当前位置标记为未访问
                    visited[x][y] = false;
                }

                // 减少步数
                step--;
            }
        }
    }
}


12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091

Python

from collections import defaultdict

# 定义一个常量数组，表示上下左右四个方向的偏移量
OFFSETS = [
    (-1, 0),
    (1, 0),
    (0, -1),
    (0, 1),
]

# 深度优先搜索函数
def dfs(x, y, step, min_step_to_height, matrix, m, n, k, memo, visited):
    # 获取当前位置的高度
    last_height = matrix[x][y]

    # 遍历四个方向
    for offset in OFFSETS:
        # 计算新的位置
        new_x = x + offset[0]
        new_y = y + offset[1]

        # 检查新位置是否在矩阵范围内
        if new_x < 0 or new_x >= m or new_y < 0 or new_y >= n:
            continue

        # 获取新位置的高度
        cur_height = matrix[new_x][new_y]

        # 检查两个位置的高度差是否在k以内
        if abs(cur_height - last_height) <= k:
            # 增加步数
            step += 1

            # 更新到达新高度的最短步数
            if cur_height not in min_step_to_height or min_step_to_height[cur_height] > step:
                min_step_to_height[cur_height] = step

            # 检查记忆化数组，避免重复计算
            if memo[new_x][new_y] == 0 or memo[new_x][new_y] > step:
                # 更新记忆化数组
                memo[new_x][new_y] = step
                # 标记当前位置为已访问
                visited[x][y] = True

                # 递归调用深度优先搜索
                dfs(new_x, new_y, step, min_step_to_height, matrix, m, n, k, memo, visited)

                # 回溯时，将当前位置标记为未访问
                visited[x][y] = False

            # 减少步数
            step -= 1

# 主函数
def main():
    # 读取输入的m, n, k
    m, n, k = map(int, input().split())
    # 初始化山地图矩阵
    matrix = [list(map(int, input().split())) for _ in range(m)]

    # 初始化一个哈希表，用于存储到达不同高度的最短步数
    min_step_to_height = {matrix[0][0]: 0}
    # 初始化一个记忆化数组，用于记录已经访问过的位置和步数
    memo = [[0] * n for _ in range(m)]
    # 初始化一个布尔数组，用于记录已经访问过的位置
    visited = [[False] * n for _ in range(m)]

    # 调用深度优先搜索函数
    dfs(0, 0, 0, min_step_to_height, matrix, m, n, k, memo, visited)

    # 计算最高峰的高度和最短步数
    max_height = max(min_step_to_height.keys())
    min_step = min_step_to_height[max_height]

    # 输出结果
    print(max_height, min_step)

# 程序入口
if __name__ == "__main__":
    main()


12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182

JavaScript

const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

// 定义一个常量数组，表示上下左右四个方向的偏移量
const OFFSETS = [
    [-1, 0],
    [1, 0],
    [0, -1],
    [0, 1],
];

// 深度优先搜索函数
function dfs(x, y, step, minStepToHeight, matrix, m, n, k, memo, visited) {
    // 获取当前位置的高度
    const lastHeight = matrix[x][y];

    // 遍历四个方向
    for (const offset of OFFSETS) {
        // 计算新的位置
        const newX = x + offset[0];
        const newY = y + offset[1];

        // 检查新位置是否在矩阵范围内
        if (newX < 0 || newX >= m || newY < 0 || newY >= n) {
            continue;
        }

        // 获取新位置的高度
        const curHeight = matrix[newX][newY];

        // 检查两个位置的高度差是否在k以内
        if (Math.abs(curHeight - lastHeight) <= k) {
            // 增加步数
            step += 1;

            // 更新到达新高度的最短步数
            if (!(curHeight in minStepToHeight) || minStepToHeight[curHeight] > step) {
                minStepToHeight[curHeight] = step;
            }

            // 检查记忆化数组，避免重复计算
            if (memo[newX][newY] === 0 || memo[newX][newY] > step) {
                // 更新记忆化数组
                memo[newX][newY] = step;
                // 标记当前位置为已访问
                visited[x][y] = true;

                // 递归调用深度优先搜索
                dfs(newX, newY, step, minStepToHeight, matrix, m, n, k, memo, visited);

                // 回溯时，将当前位置标记为未访问
                visited[x][y] = false;
            }

            // 减少步数
            step -= 1;
        }
    }
}
const inputLines = [];

rl.on('line', input => {
    inputLines.push(input);
    if (inputLines.length === parseInt(inputLines[0].split(' ')[0], 10) + 1) {
        rl.close();
        const [m, n, k] = inputLines[0].split(' ').map(Number);
        const matrix = inputLines.slice(1).map(line => line.split(' ').map(Number));


        // 初始化一个哈希表，用于存储到达不同高度的最短步数
        const minStepToHeight = { [matrix[0][0]]: 0 };
        // 初始化一个记忆化数组，用于记录已经访问过的位置和步数
        const memo = Array.from({ length: m }, () => Array(n).fill(0));
        // 初始化一个布尔数组，用于记录已经访问过的位置
        const visited = Array.from({ length: m }, () => Array(n).fill(false));

        // 调用深度优先搜索函数
        dfs(0, 0, 0, minStepToHeight, matrix, m, n, k, memo, visited);

        // 计算最高峰的高度和最短步数
        const max_height = Math.max(...Object.keys(minStepToHeight).map(Number));
        const min_step = minStepToHeight[max_height];

        // 输出结果
        console.log(max_height, min_step);

        rl.close();
    }
})




123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596

C++

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

// 定义一个常量数组，表示上下左右四个方向的偏移量
const vector<vector<int>> OFFSETS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

// 深度优先搜索函数
void dfs(int x, int y, int step, unordered_map<int, int> &minStepToHeight, vector<vector<int>> &matrix, int m, int n, int k, vector<vector<int>> &memo, vector<vector<bool>> &visited) {
    // 获取当前位置的高度
    int lastHeight = matrix[x][y];

    // 遍历四个方向
    for (const auto &offset : OFFSETS) {
        // 计算新的位置
        int newX = x + offset[0];
        int newY = y + offset[1];

        // 检查新位置是否在矩阵范围内
        if (newX < 0 || newX >= m || newY < 0 || newY >= n) continue;

        // 获取新位置的高度
        int curHeight = matrix[newX][newY];

        // 检查两个位置的高度差是否在k以内
        if (abs(curHeight - lastHeight) <= k) {
            // 增加步数
            step++;

            // 更新到达新高度的最短步数
            if (minStepToHeight.find(curHeight) == minStepToHeight.end() || minStepToHeight[curHeight] > step) {
                minStepToHeight[curHeight] = step;
            }

            // 检查记忆化数组，避免重复计算
            if (memo[newX][newY] == 0 || memo[newX][newY] > step) {
                // 更新记忆化数组
                memo[newX][newY] = step;
                // 标记当前位置为已访问
                visited[x][y] = true;

                // 递归调用深度优先搜索
                dfs(newX, newY, step, minStepToHeight, matrix, m, n, k, memo, visited);

                // 回溯时，将当前位置标记为未访问
                visited[x][y] = false;
            }

            // 减少步数
            step--;
        }
    }
}

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

    // 初始化山地图矩阵
    vector<vector<int>> matrix(m, vector<int>(n));
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            cin >> matrix[i][j];
        }
    }

    // 初始化一个哈希表，用于存储到达不同高度的最短步数
    unordered_map<int, int> minStepToHeight;
    minStepToHeight[matrix[0][0]] = 0;

    // 初始化一个记忆化数组，用于记录已经访问过的位置和步数
    vector<vector<int>> memo(m, vector<int>(n));
    // 初始化一个布尔数组，用于记录已经访问过的位置
    vector<vector<bool>> visited(m, vector<bool>(n));
    // 调用深度优先搜索函数
    dfs(0, 0, 0, minStepToHeight, matrix, m, n, k, memo, visited);

    // 计算最高峰的高度和最短步数
    int maxHeight = 0;
    int minStep = 0;
    for (const auto &entry : minStepToHeight) {
        if (entry.first > maxHeight) {
            maxHeight = entry.first;
            minStep = entry.second;
        }
    }

    // 输出结果
    cout << maxHeight << " " << minStep << endl;

    return 0;
}


12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697

C语言

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>

// 定义四个方向的偏移量：上、下、左、右
int OFFSETS[4][2] = {
    {-1, 0},  // 上
    {1, 0},   // 下
    {0, -1},  // 左
    {0, 1}    // 右
};

// 深度优先搜索函数
void dfs(int x, int y, int step, int **minStepToHeight, int **matrix, int m, int n, int k, int **memo, bool **visited) {
    // 获取当前位置的高度
    int lastHeight = matrix[x][y];

    // 遍历四个方向
    for (int i = 0; i < 4; i++) {
        int newX = x + OFFSETS[i][0];  // 新位置的行坐标
        int newY = y + OFFSETS[i][1];  // 新位置的列坐标

        // 检查新位置是否在地图范围内
        if (newX < 0 || newX >= m || newY < 0 || newY >= n) {
            continue;
        }

        // 获取新位置的高度
        int curHeight = matrix[newX][newY];

        // 检查高度差是否在k以内
        if (abs(curHeight - lastHeight) <= k) {
            step++;  // 增加步数

            // 更新到达新高度的最短步数
            if (minStepToHeight[curHeight][0] == 0 || minStepToHeight[curHeight][0] > step) {
                minStepToHeight[curHeight][0] = step;
            }

            // 检查记忆数组，避免重复计算
            if (memo[newX][newY] == 0 || memo[newX][newY] > step) {
                memo[newX][newY] = step;    // 更新记忆化数组
                visited[x][y] = true;       // 标记当前位置为已访问

                // 递归调用深度优先搜索
                dfs(newX, newY, step, minStepToHeight, matrix, m, n, k, memo, visited);

                visited[x][y] = false;      // 回溯时标记当前位置为未访问
            }

            step--;  // 回溯时步数减少
        }
    }
}

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

    // 动态分配二维数组用于存储山地图
    int **matrix = (int **)malloc(m * sizeof(int *));
    for (int i = 0; i < m; i++) {
        matrix[i] = (int *)malloc(n * sizeof(int));
        for (int j = 0; j < n; j++) {
            scanf("%d", &matrix[i][j]);  // 读取山地图
        }
    }

    // 初始化用于存储到达不同高度的最短步数数组
    int **minStepToHeight = (int **)malloc(10 * sizeof(int *));
    for (int i = 0; i < 10; i++) {
        minStepToHeight[i] = (int *)calloc(1, sizeof(int));  // 初始最短步数为0
    }

    // 初始化记忆化数组，用于记录已经访问过的位置和步数
    int **memo = (int **)malloc(m * sizeof(int *));
    for (int i = 0; i < m; i++) {
        memo[i] = (int *)calloc(n, sizeof(int));
    }

    // 初始化访问数组，记录已访问位置
    bool **visited = (bool **)malloc(m * sizeof(bool *));
    for (int i = 0; i < m; i++) {
        visited[i] = (bool *)calloc(n, sizeof(bool));
    }

    // 初始化时从起点 (0,0) 开始
    minStepToHeight[matrix[0][0]][0] = 0;

    // 调用深度优先搜索
    dfs(0, 0, 0, minStepToHeight, matrix, m, n, k, memo, visited);

    // 查找能够到达的最高峰及其最短步数
    int max_height = 0;
    int min_step = 0;

    for (int i = 0; i < 10; i++) {
        if (minStepToHeight[i][0] != 0) {
            max_height = i;      // 更新最高峰高度
            min_step = minStepToHeight[i][0];  // 获取最短步数
        }
    }

    // 输出结果，如果无法到达任何峰值，输出0 0
    if (max_height == 0) {
        printf("0 0\n");
    } else {
        printf("%d %d\n", max_height, min_step);
    }

    // 释放动态分配的内存
    for (int i = 0; i < m; i++) {
        free(matrix[i]);
        free(memo[i]);
        free(visited[i]);
    }
    free(matrix);
    free(memo);
    free(visited);

    for (int i = 0; i < 10; i++) {
        free(minStepToHeight[i]);
    }
    free(minStepToHeight);

    return 0;
}
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128
#牛客创作赏金赛#
大厂原题(全网最全，持续更新) 文章被收录于专栏

主要记录自己的刷题日常，学而时习之。

全部评论

相关推荐

11-18 08:48
沈阳工业大学 研发工程师
机考E卷200分题 - 转骰子
题目描述&nbsp;骰子是一个立方体，每个面一个数字，初始为左1，右2，前3(观察者方向)，后4，上5，下6，用123456表示这个状态，放置在平面上，&nbsp;可以向左翻转(用L表示向左翻转1次)，&nbsp;可以向右翻转(用R表示向右翻转1次)，&nbsp;可以向前翻转(用F表示向前翻转1次)，&nbsp;可以向后翻转(用B表示向后翻转1次)，&nbsp;可以逆时针旋转(用A表示逆时针旋转90度)，&nbsp;可以顺时针旋转(用C表示顺时针旋转90度)，&nbsp;现从123456这个初始状态开始，根据输入的动作序列，计算得到最终的状态。&nbsp;骰子的初始状态和初始状态转动后的状态如图所示。&nbsp;输入描述&nbsp;输入一行，为只包含LRFBAC的字母序列，最大长度为50，字母可...
大厂原题(全网最全，持续... 牛客创作赏金赛
点赞 评论 收藏
分享
11-17 19:26
武汉理工大学 机械设计/制造
点赞 评论 收藏
分享
10-27 01:10
门头沟学院 算法工程师
点赞 评论 收藏
分享
11-01 09:34
已编辑
门头沟学院 Java
华为校招最新消息
投递华为等公司10个岗位
点赞 评论 收藏
分享
10-25 18:14
门头沟学院 Java
华为求捞
之前数字能源9.27笔试挂了，想转投终端部，求hr捞
aloffer：别终端了，终端炸死了，人多的要死
投递华为等公司10个岗位 >
点赞 评论 收藏
分享
点赞 收藏 评论
分享

招聘动态

查看更多

杉川机器人

2025校园招聘

字节跳动

2025校园招聘

字节跳动Data

2025校园招聘

快手Star

2025届招聘

快手

销售类投递专区

库洛游戏

全站热榜

正在热议
# 晒一晒我的offer #
9704721次浏览 104821人参与
# 机械只有读研才有出路吗？ #
7901次浏览 103人参与
# 北方华创开奖 #
21031次浏览 244人参与
# 地方国企笔面经互助 #
1908次浏览 6人参与
# 滴滴求职进展汇总 #
78766次浏览 688人参与
# 考研失败就一定是坏事吗？ #
36266次浏览 355人参与
# 机械人，签完三方你在忙什么？ #
22965次浏览 119人参与
# 总结:哪家公司面试体验感最差 #
23450次浏览 115人参与
# 机械应届生薪资要多少才合适？ #
11753次浏览 55人参与
# 学历or实习经历，哪个更重要 #
39053次浏览 280人参与
# 选完offer后，你后悔学本专业吗 #
6556次浏览 43人参与
# 查收我的offer竞争力报告 #
13300次浏览 191人参与
# 机械人怎么评价今年的比亚迪 #
40872次浏览 141人参与
# 应届生被毁约被毁意向了怎么办 #
24055次浏览 230人参与
# 00后45度躺现状 #
33485次浏览 294人参与
# 没有合适的工作，你会先找个干着，还是考公考研 #
35301次浏览 392人参与
# 秋招OC许愿 #
224022次浏览 1854人参与
# 如果能重来，就业or读研你选哪个？ #
45262次浏览 333人参与
# 大疆求职进展汇总 #
402634次浏览 2869人参与
# 实习，投递多份简历没人回复怎么办 #
2381538次浏览 34165人参与
# 双非能在秋招上岸吗？ #
98953次浏览 768人参与
牛客网
牛客企业服务