华为OD机试E卷 -周末爬山（Java & Python& JS & C++ & C ）

https://blog.csdn.net/banxia_frontend/article/details/141961897

最新华为OD机试

真题目录：点击查看目录 华为OD面试真题精选：点击立即查看

题目描述

周末小明准备去爬山锻炼，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

输出

2 2

说明

根据山地图可知，能爬到的最高峰在(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

输出

0 0

说明

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

解题思路

题目解析

这是一道经典的路径搜索题目，可以通过 广度优先搜索（BFS） 来解决。题目要求小明从左上角（起点）出发，按照一定的规则找到能爬到的 最高山峰，并输出到达该山峰的 最短路径长度。

题目中的关键点包括：

1. 地图表示：地图是一个二维数组，每个位置表示山的高度，0 表示平地，1-9 表示不同高度的山峰。
2. 高度差限制：每次移动到的格子，高度差不能超过给定值 k，否则不能前进。
3. 移动规则：每次只能上下左右移动一个格子。
4. 结果要求：
   • 如果小明能爬到更高的山峰，则输出该山峰的高度和到达该山峰的最短步数。
   • 如果小明无法爬到更高的山峰（只能停留在起点或平地），则输出 0 0。

解题思路

1. 广度优先搜索（BFS）

• BFS 特点：逐层扩展，保证先找到的是最短路径。因此，BFS 非常适合用来求解最短路径问题。
• 我们从起点 (0, 0) 开始，按照上下左右四个方向尝试移动，检查是否符合规则：
  1. 新位置没有越界。
  2. 高度差不超过 k。
  3. 新位置没有被更短路径访问过（保证路径最短）。

2. 数据结构

• 队列 (Queue)：存储当前可以扩展的位置，每次取队头的点进行扩展。
• 访问记录 (minSteps)：记录从起点到每个点的最短步数，避免重复访问。
• 二维数组 (heightMap)：表示地图中每个位置的高度。

3. BFS 流程

1. 初始化：
   • 将起点 (0, 0) 加入队列，步数为 0。
   • 将访问记录数组 minSteps 的起点步数设置为 0。
2. 队列循环：
   • 每次从队列中取出一个点 (x, y) 和当前步数 steps。
   • 遍历当前点的四个方向 (nx, ny)，判断是否可以移动到新位置：
     • 新位置未越界。
     • 高度差满足限制。
     • 新位置尚未被更短路径访问。
   • 如果满足条件，将新位置 (nx, ny) 加入队列，并更新访问记录。
3. 更新结果：
   • 如果当前移动到的山峰高度大于已知的最高山峰高度，则更新最高山峰高度和到达的最短路径。
   • 如果高度相同，则比较路径步数，保留更短的路径。

4. 结果输出

• 如果能找到更高的山峰，输出其高度和最短路径。
• 如果无法找到更高的山峰，输出 0 0。

---

Java

import java.util.*;

public class Main {
    // 定义四个方向数组，用于表示上下左右移动
    static int[][] DIRS = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};

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

        // 读取输入的地图大小(m, n)和最大高度差k
        int rows = sc.nextInt(); // 地图行数
        int cols = sc.nextInt(); // 地图列数
        int maxDiff = sc.nextInt(); // 最大允许的高度差

        // 读取地图高度信息
        int[][] heightMap = new int[rows][cols];
        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                heightMap[i][j] = sc.nextInt();
            }
        }

        // 队列存储当前坐标(x, y)及到该位置的步数steps
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{0, 0, 0}); // 从起点(0,0)开始，初始步数为0

        // 记录从起点到各个点的最短步数
        int[][] minSteps = new int[rows][cols];
        for (int[] row : minSteps) {
            Arrays.fill(row, Integer.MAX_VALUE); // 初始化为最大值，表示未访问
        }
        minSteps[0][0] = 0; // 起点的步数为0

        // 记录能到达的最高山峰高度和到达该山峰的最短路径
        int maxHeight = heightMap[0][0];
        int minRoute = 0;

        // 广度优先搜索(BFS)遍历地图
        while (!queue.isEmpty()) {
            int[] current = queue.poll(); // 取出当前节点
            int x = current[0]; // 当前x坐标
            int y = current[1]; // 当前y坐标
            int steps = current[2]; // 当前步数

            // 遍历上下左右四个方向
            for (int[] dir : DIRS) {
                int nx = x + dir[0]; // 新的x坐标
                int ny = y + dir[1]; // 新的y坐标

                // 判断是否可以移动到新位置
                if (nx >= 0 && nx < rows && ny >= 0 && ny < cols && // 边界条件
                    Math.abs(heightMap[nx][ny] - heightMap[x][y]) <= maxDiff && // 高度差限制
                    steps + 1 < minSteps[nx][ny]) { // 检查是否是更短路径

                    // 将新位置加入队列
                    queue.add(new int[]{nx, ny, steps + 1});
                    minSteps[nx][ny] = steps + 1; // 更新到新位置的最短步数

                    // 更新最高山峰和最短路径
                    if (heightMap[nx][ny] > maxHeight) {
                        maxHeight = heightMap[nx][ny]; // 更新最高山峰
                        minRoute = steps + 1; // 更新到最高山峰的最短路径
                    } else if (heightMap[nx][ny] == maxHeight && steps + 1 < minRoute) {
                        minRoute = steps + 1; // 如果高度相同，选择更短路径
                    }
                }
            }
        }

        // 输出结果
        // 如果能到达比起点更高的山峰，输出山峰高度和到达步数；否则输出0 0
        if (maxHeight > heightMap[0][0]) {
            System.out.println(maxHeight + " " + minRoute);
        } else {
            System.out.println("0 0");
        }
    }
}

Python

from collections import deque

# 定义四个方向数组，用于表示上下左右移动
DIRECTIONS = [(0, 1), (1, 0), (-1, 0), (0, -1)]

def main():
    # 读取输入的地图大小(m, n)和最大高度差k
    rows, cols, max_diff = map(int, input().split())

    # 读取地图高度信息
    height_map = []
    for _ in range(rows):
        height_map.append(list(map(int, input().split())))

    # 队列存储当前坐标(x, y)及到该位置的步数steps
    queue = deque([(0, 0, 0)])  # 从起点(0,0)开始，初始步数为0

    # 记录从起点到各个点的最短步数
    min_steps = [[float('inf')] * cols for _ in range(rows)]
    min_steps[0][0] = 0  # 起点的步数为0

    # 记录能到达的最高山峰高度和到达该山峰的最短路径
    max_height = height_map[0][0]
    min_route = 0

    # 广度优先搜索(BFS)遍历地图
    while queue:
        x, y, steps = queue.popleft()  # 取出当前节点

        # 遍历上下左右四个方向
        for dx, dy in DIRECTIONS:
            nx, ny = x + dx, y + dy  # 新的坐标

            # 判断是否可以移动到新位置
            if 0 <= nx < rows and 0 <= ny < cols and \
               abs(height_map[nx][ny] - height_map[x][y]) <= max_diff and \
               steps + 1 < min_steps[nx][ny]:

                # 将新位置加入队列
                queue.append((nx, ny, steps + 1))
                min_steps[nx][ny] = steps + 1  # 更新到新位置的最短步数

                # 更新最高山峰和最短路径
                if height_map[nx][ny] > max_height:
                    max_height = height_map[nx][ny]  # 更新最高山峰
                    min_route = steps + 1  # 更新到最高山峰的最短路径
                elif height_map[nx][ny] == max_height and steps + 1 < min_route:
                    min_route = steps + 1  # 如果高度相同，选择更短路径

    # 输出结果
    # 如果能到达比起点更高的山峰，输出山峰高度和到达步数；否则输出0 0
    if max_height > height_map[0][0]:
        print(max_height, min_route)
    else:
        print(0, 0)

if __name__ == "__main__":
    main()

JavaScript

const readline = require('readline');

// 定义四个方向数组，用于表示上下左右移动
const DIRS = [
    [0, 1],  // 向右
    [1, 0],  // 向下
    [-1, 0], // 向上
    [0, -1]  // 向左
];

// 创建读取行的接口
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

let lines = [];
rl.on('line', (line) => {
    lines.push(line);
}).on('close', () => {
    // 读取输入的地图大小(rows, cols)和最大高度差(maxDiff)
    const [rows, cols, maxDiff] = lines.shift().split(' ').map(Number);

    // 读取地图高度信息
    const heightMap = lines.map(line => line.split(' ').map(Number));

    // 队列存储当前坐标(x, y)及到该位置的步数steps
    const queue = [[0, 0, 0]];  // 从起点(0, 0)开始，初始步数为0

    // 初始化最短步数数组
    const minSteps = Array.from({ length: rows }, () => Array(cols).fill(Infinity));
    minSteps[0][0] = 0;  // 起点的步数为0

    // 记录最高山峰的高度和到达该山峰的最短路径
    let maxHeight = heightMap[0][0];
    let minRoute = 0;

    // 广度优先搜索(BFS)
    while (queue.length > 0) {
        const [x, y, steps] = queue.shift();  // 取出当前节点

        // 遍历上下左右四个方向
        DIRS.forEach(([dx, dy]) => {
            const nx = x + dx;
            const ny = y + dy;

            // 检查是否可以移动到新位置
            if (nx >= 0 && nx < rows && ny >= 0 && ny < cols &&
                Math.abs(heightMap[nx][ny] - heightMap[x][y]) <= maxDiff &&
                steps + 1 < minSteps[nx][ny]) {
                
                queue.push([nx, ny, steps + 1]);  // 将新位置加入队列
                minSteps[nx][ny] = steps + 1;  // 更新到新位置的最短步数

                // 更新最高山峰和最短路径
                if (heightMap[nx][ny] > maxHeight) {
                    maxHeight = heightMap[nx][ny];
                    minRoute = steps + 1;
                } else if (heightMap[nx][ny] === maxHeight && steps + 1 < minRoute) {
                    minRoute = steps + 1;  // 如果高度相同，选择更短路径
                }
            }
        });
    }

    // 输出结果
    if (maxHeight > heightMap[0][0]) {
        console.log(`${maxHeight} ${minRoute}`);
    } else {
        console.log("0 0");
    }
});

C++

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <climits>

using namespace std;

// 定义四个方向数组，用于表示上下左右移动
const int DIRS[4][2] = {
    {0, 1},  // 右
    {1, 0},  // 下
    {-1, 0}, // 上
    {0, -1}  // 左
};

int main() {
    int rows, cols, maxDiff;
    cin >> rows >> cols >> maxDiff;

    // 读取地图高度信息
    vector<vector<int>> heightMap(rows, vector<int>(cols));
    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < cols; ++j) {
            cin >> heightMap[i][j];
        }
    }

    // 队列用于存储当前坐标(x, y)及到达该位置的步数(steps)
    queue<tuple<int, int, int>> q; // tuple存储(x, y, steps)
    q.push({0, 0, 0}); // 起点为(0, 0)，初始步数为0

    // 初始化最短步数矩阵
    vector<vector<int>> minSteps(rows, vector<int>(cols, INT_MAX));
    minSteps[0][0] = 0; // 起点步数为0

    // 记录最高山峰的高度和到达该山峰的最短路径
    int maxHeight = heightMap[0][0];
    int minRoute = 0;

    // 广度优先搜索(BFS)
    while (!q.empty()) {
        auto [x, y, steps] = q.front(); // 取出当前节点
        q.pop();

        // 遍历上下左右四个方向
        for (const auto& dir : DIRS) {
            int nx = x + dir[0]; // 新的x坐标
            int ny = y + dir[1]; // 新的y坐标

            // 检查是否满足移动条件
            if (nx >= 0 && nx < rows && ny >= 0 && ny < cols && // 边界检查
                abs(heightMap[nx][ny] - heightMap[x][y]) <= maxDiff && // 高度差限制
                steps + 1 < minSteps[nx][ny]) { // 是否为更短路径

                // 更新最短步数矩阵并加入队列
                minSteps[nx][ny] = steps + 1;
                q.push({nx, ny, steps + 1});

                // 更新最高山峰高度和最短路径
                if (heightMap[nx][ny] > maxHeight) {
                    maxHeight = heightMap[nx][ny];
                    minRoute = steps + 1;
                } else if (heightMap[nx][ny] == maxHeight && steps + 1 < minRoute) {
                    minRoute = steps + 1; // 如果高度相同，选择更短路径
                }
            }
        }
    }

    // 输出结果
    if (maxHeight > heightMap[0][0]) {
        cout << maxHeight << " " << minRoute << endl;
    } else {
        cout << "0 0" << endl;
    }

    return 0;
}

C语言

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

// 定义四个方向数组，用于表示上下左右移动
const int DIRS[4][2] = {
    {0, 1},  // 右
    {1, 0},  // 下
    {-1, 0}, // 上
    {0, -1}  // 左
};

typedef struct {
    int x, y, steps;
} Node;

typedef struct {
    Node *data;
    int front, rear, size, capacity;
} Queue;

// 初始化队列
Queue* createQueue(int capacity) {
    Queue* queue = (Queue*)malloc(sizeof(Queue));
    queue->capacity = capacity;
    queue->front = 0;
    queue->size = 0;
    queue->rear = -1;
    queue->data = (Node*)malloc(capacity * sizeof(Node));
    return queue;
}

// 队列操作
int isQueueEmpty(Queue* queue) {
    return queue->size == 0;
}

void enqueue(Queue* queue, int x, int y, int steps) {
    queue->rear = (queue->rear + 1) % queue->capacity;
    queue->data[queue->rear].x = x;
    queue->data[queue->rear].y = y;
    queue->data[queue->rear].steps = steps;
    queue->size++;
}

Node dequeue(Queue* queue) {
    Node item = queue->data[queue->front];
    queue->front = (queue->front + 1) % queue->capacity;
    queue->size--;
    return item;
}

int main() {
    int rows, cols, maxDiff;
    scanf("%d %d %d", &rows, &cols, &maxDiff);

    // 读取地图高度信息
    int** heightMap = (int**)malloc(rows * sizeof(int*));
    for (int i = 0; i < rows; i++) {
        heightMap[i] = (int*)malloc(cols * sizeof(int));
        for (int j = 0; j < cols; j++) {
            scanf("%d", &heightMap[i][j]);
        }
    }

    // 初始化最短步数矩阵
    int** minSteps = (int**)malloc(rows * sizeof(int*));
    for (int i = 0; i < rows; i++) {
        minSteps[i] = (int*)malloc(cols * sizeof(int));
        for (int j = 0; j < cols; j++) {
            minSteps[i][j] = INT_MAX;
        }
    }
    minSteps[0][0] = 0;

    // 创建队列
    Queue* queue = createQueue(rows * cols);
    enqueue(queue, 0, 0, 0);

    // 记录最高山峰的高度和最短路径
    int maxHeight = heightMap[0][0];
    int minRoute = 0;

    // 广度优先搜索(BFS)
    while (!isQueueEmpty(queue)) {
        Node current = dequeue(queue);
        int x = current.x;
        int y = current.y;
        int steps = current.steps;

        // 遍历上下左右四个方向
        for (int i = 0; i < 4; i++) {
            int nx = x + DIRS[i][0];
            int ny = y + DIRS[i][1];

            // 检查是否满足移动条件
            if (nx >= 0 && nx < rows && ny >= 0 && ny < cols &&
                abs(heightMap[nx][ny] - heightMap[x][y]) <= maxDiff &&
                steps + 1 < minSteps[nx][ny]) {

                minSteps[nx][ny] = steps + 1;
                enqueue(queue, nx, ny, steps + 1);

                if (heightMap[nx][ny] > maxHeight) {
                    maxHeight = heightMap[nx][ny];
                    minRoute = steps + 1;
                } else if (heightMap[nx][ny] == maxHeight && steps + 1 < minRoute) {
                    minRoute = steps + 1;
                }
            }
        }
    }

    // 输出结果
    if (maxHeight > heightMap[0][0]) {
        printf("%d %d\n", maxHeight, minRoute);
    } else {
        printf("0 0\n");
    }

    // 释放内存
    for (int i = 0; i < rows; i++) {
        free(heightMap[i]);
        free(minSteps[i]);
    }
    free(heightMap);
    free(minSteps);
    free(queue->data);
    free(queue);

    return 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

用例2

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

用例3

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

用例4

2 2 3
3 1
1 3

用例5

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

用例6

4 4 2
1 1 1 1
1 9 1 1
1 1 1 1
1 1 1 1

用例7

4 4 1 
0 1 2 3
1 2 3 4
2 3 4 5
3 4 5 6

用例8

4 5 2
1 1 1 1 1
1 2 3 4 5
1 2 3 4 5
1 1 1 1 1

用例9

2 2 4
1 9
2 8

用例10

3 3 1
1 1 2
2 9 2
1 1 2