目录

题目

思路

Code

题目

给定一个二维数组mountainMap表示一座山的地图，数组中的每个元素mountainMap[x][y]代表坐标(x,y)处山的高度。登山员从山底出发，爬到山峰。
山底的含义:mountainMap中高度为0的坐标点，
山峰的含义:mountainMap中高度最高的坐标点，
山底和山峰有且仅有一个坐标。
登山员每次移动只能从当前位置向上下左右四个方向移动一格，向高处移动时，移动到的位置的山的高度不能高干当前位置山的高度加上固定的攀爬能力值climmbAbility.向低处移动时，移动到的位置的山的高度不能低于当前位置山的高度减去climbAbility。
请计算出从山底移动到山峰，最少需要移动几次?

输入描述
1.第-行为climbAbility的值
2.第二行为mountainMapRows mountainMapCols
3.从第三行开始为mountainMapRows行mountainMapCols列的高度二维数组mountainMap|mountainMapRous][mountainMapCols]，每行的高度数字中间用空格分割

climbAbility:[1,30]
山峰高度:[0, 100]
mountainMap的行数mountainMapRows:[2,1000]
mountainMap的列数mountainMapCols:[2,1000]

输出描述
从山底移动到山峰，最少移动次数。
如果无法移动至山峰，则输出一1

示例1：
输入：
2
3 2
1 3
0 4
5 3

输出：
5
说明：
攀登能力为2，3行2列的山峰坐标，山底的坐标为(1,0)高度0，山峰的坐标为(2,0)高度5。仅有一条路线初始位置山底(1,0)高度0->(0,0)高度1->(0,1)高度3->(1,1)高度4->(2,1)高度3->(2,0)高度5共需要移动5次

示例2：
输入：
1
4 5
1 1 1 1 1
1 0 1 2 1
1 1 1 3 1
1 1 1 1 1

输出：
3
说明：
攀登能力为1，4行5列的山峰坐标，山底的坐标为(1,1)，山峰的坐标为(2,3)。
最短路线为
初始位置山底(1,1)高度0- >(1,2)高度1- >(1,3)高度2- >山峰(2,3)高度3共需要移动3次

思路

1. 问题分析

1.1 题目理解

输出要求：

• 计算从山底到山峰的最少移动次数

• 如果无法到达山峰，输出-1

约束条件：

• 攀爬能力值climbAbility范围：[1,30]

• 山峰高度范围：[0,100]

• 地图行数范围：[2,1000]

• 地图列数范围：[2,1000]

• 每次只能向上下左右四个方向移动一格

• 向高处移动：新高度 ≤ 当前高度 + climbAbility

• 向低处移动：新高度 ≥ 当前高度 - climbAbility

• 山底和山峰各只有一个坐标点

1.2 问题建模

数据结构：

• 使用二维数组表示山地图

• 使用坐标对表示位置

• 使用队列存储待探索的位置

算法类型：

• 本质是一个带约束条件的最短路径问题

• 可以使用广度优先搜索(BFS)求解最短路径

2. 解题思路

2.1 算法选择

最优算法：

• 选择BFS算法，因为需要找最短路径

• BFS能保证首次到达目标点时就是最短路径

复杂度分析：

• 时间复杂度：O(R×C)，R为行数，C为列数

• 空间复杂度：O(R×C)，用于存储访问状态

2.2 核心数据结构

主要数据结构：

• 二维数组：存储山地图

• 队列：BFS搜索使用

• 访问数组：记录已访问的位置

• 方向数组：表示四个移动方向

操作复杂度：

• 队列操作：O(1)

• 位置检查：O(1)

• 方向遍历：O(1)，固定4个方向

2.3 关键算法步骤

1. 初始化

• 找到山底和山峰坐标

• 初始化访问数组

• 初始化BFS队列

1. BFS搜索

• 从山底开始BFS

• 检查每个方向的可行性

• 记录移动步数

• 直到找到山峰或搜索完所有可能路径

1. 可行性检查

• 检查新位置是否在地图范围内

• 检查高度差是否满足攀爬能力限制

• 检查是否已访问过

Python

from collections import deque
from typing import List, Tuple

def find_shortest_path(climb_ability: int, mountain_map: List[List[int]]) -> int:
    """
    使用BFS寻找从山底到山峰的最短路径
    
    Args:
        climb_ability: 攀爬能力值
        mountain_map: 山地图二维数组
    
    Returns:
        最短路径长度，如果无法到达则返回-1
    """
    rows, cols = len(mountain_map), len(mountain_map[0])
    
    # 找到山底和山峰坐标
    bottom = peak = None
    max_height = float('-inf')
    for i in range(rows):
        for j in range(cols):
            if mountain_map[i][j] == 0:
                bottom = (i, j)
            if mountain_map[i][j] > max_height:
                max_height = mountain_map[i][j]
                peak = (i, j)
    
    # 定义四个移动方向：上、右、下、左
    directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    
    # 初始化访问数组
    visited = [[False] * cols for _ in range(rows)]
    visited[bottom[0]][bottom[1]] = True
    
    # 初始化队列，存储(坐标, 步数)
    queue = deque([(bottom, 0)])
    
    while queue:
        (curr_x, curr_y), steps = queue.popleft()
        
        # 如果到达山峰
        if (curr_x, curr_y) == peak:
            return steps
        
        # 检查四个方向
        for dx, dy in directions:
            new_x, new_y = curr_x + dx, curr_y + dy
            
            # 检查新位置是否有效
            if (0 <= new_x < rows and 
                0 <= new_y < cols and 
                not visited[new_x][new_y]):
                
                # 检查高度差是否满足攀爬能力限制
                height_diff = mountain_map[new_x][new_y] - mountain_map[curr_x][curr_y]
                if -climb_ability <= height_diff <= climb_ability:
                    visited[new_x][new_y] = True
                    queue.append(((new_x, new_y), steps + 1))
    
    # 如果无法到达山峰
    return -1

def main():
    # 读取输入
    climb_ability = int(input())
    rows, cols = map(int, input().split())
    mountain_map = []
    for _ in range(rows):
        mountain_map.append(list(map(int, input().split())))
    
    # 计算并输出结果
    result = find_shortest_path(climb_ability, mountain_map)
    print(result)

if __name__ == "__main__":
    main()

 Java

import java.util.*;

public class MountainClimbing {
    static class Position {
        int x, y, steps;
        
        Position(int x, int y, int steps) {
            this.x = x;
            this.y = y;
            this.steps = steps;
        }
    }
    
    public static int findShortestPath(int climbAbility, int[][] mountainMap) {
        int rows = mountainMap.length;
        int cols = mountainMap[0].length;
        
        // 找到山底和山峰
        Position bottom = null, peak = null;
        int maxHeight = Integer.MIN_VALUE;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (mountainMap[i][j] == 0) {
                    bottom = new Position(i, j, 0);
                }
                if (mountainMap[i][j] > maxHeight) {
                    maxHeight = mountainMap[i][j];
                    peak = new Position(i, j, 0);
                }
            }
        }
        
        // 定义四个方向
        int[][] directions = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
        
        // 初始化访问数组
        boolean[][] visited = new boolean[rows][cols];
        visited[bottom.x][bottom.y] = true;
        
        // BFS队列
        Queue<Position> queue = new LinkedList<>();
        queue.offer(bottom);
        
        while (!queue.isEmpty()) {
            Position curr = queue.poll();
            
            // 到达山峰
            if (curr.x == peak.x && curr.y == peak.y) {
                return curr.steps;
            }
            
            // 检查四个方向
            for (int[] dir : directions) {
                int newX = curr.x + dir[0];
                int newY = curr.y + dir[1];
                
                if (isValid(newX, newY, rows, cols) && !visited[newX][newY]) {
                    int heightDiff = mountainMap[newX][newY] - mountainMap[curr.x][curr.y];
                    
                    if (Math.abs(heightDiff) <= climbAbility) {
                        visited[newX][newY] = true;
                        queue.offer(new Position(newX, newY, curr.steps + 1));
                    }
                }
            }
        }
        
        return -1;
    }
    
    private static boolean isValid(int x, int y, int rows, int cols) {
        return x >= 0 && x < rows && y >= 0 && y < cols;
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 读取输入
        int climbAbility = scanner.nextInt();
        int rows = scanner.nextInt();
        int cols = scanner.nextInt();
        
        int[][] mountainMap = new int[rows][cols];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                mountainMap[i][j] = scanner.nextInt();
            }
        }
        
        // 计算并输出结果
        System.out.println(findShortestPath(climbAbility, mountainMap));
    }
}

 C++

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

struct Position {
    int x, y, steps;
    Position(int x, int y, int steps) : x(x), y(y), steps(steps) {}
};

class Solution {
public:
    int findShortestPath(int climbAbility, vector<vector<int>>& mountainMap) {
        int rows = mountainMap.size();
        int cols = mountainMap[0].size();
        
        // 找到山底和山峰
        Position *bottom = nullptr, *peak = nullptr;
        int maxHeight = INT_MIN;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (mountainMap[i][j] == 0) {
                    bottom = new Position(i, j, 0);
                }
                if (mountainMap[i][j] > maxHeight) {
                    maxHeight = mountainMap[i][j];
                    peak = new Position(i, j, 0);
                }
            }
        }
        
        // 定义四个方向
        vector<pair<int, int>> directions = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
        
        // 初始化访问数组
        vector<vector<bool>> visited(rows, vector<bool>(cols, false));
        visited[bottom->x][bottom->y] = true;
        
        // BFS队列
        queue<Position> q;
        q.push(*bottom);
        
        while (!q.empty()) {
            Position curr = q.front();
            q.pop();
            
            // 到达山峰
            if (curr.x == peak->x && curr.y == peak->y) {
                delete bottom;
                delete peak;
                return curr.steps;
            }
            
            // 检查四个方向
            for (const auto& dir : directions) {
                int newX = curr.x + dir.first;
                int newY = curr.y + dir.second;
                
                if (isValid(newX, newY, rows, cols) && !visited[newX][newY]) {
                    int heightDiff = mountainMap[newX][newY] - mountainMap[curr.x][curr.y];
                    
                    if (abs(heightDiff) <= climbAbility) {
                        visited[newX][newY] = true;
                        q.push(Position(newX, newY, curr.steps + 1));
                    }
                }
            }
        }
        
        delete bottom;
        delete peak;
        return -1;
    }
    
private:
    bool isValid(int x, int y, int rows, int cols) {
        return x >= 0 && x < rows && y >= 0 && y < cols;
    }
};

int main() {
    int climbAbility, rows, cols;
    cin >> climbAbility >> rows >> cols;
    
    vector<vector<int>> mountainMap(rows, vector<int>(cols));
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            cin >> mountainMap[i][j];
        }
    }
    
    Solution solution;
    cout << solution.findShortestPath(climbAbility, mountainMap) << endl;
    
    return 0;
}

 JavaScript

class Position {
    constructor(x, y, steps) {
        this.x = x;
        this.y = y;
        this.steps = steps;
    }
}

function findShortestPath(climbAbility, mountainMap) {
    const rows = mountainMap.length;
    const cols = mountainMap[0].length;
    
    // 找到山底和山峰
    let bottom = null, peak = null;
    let maxHeight = -Infinity;
    
    for (let i = 0; i < rows; i++) {
        for (let j = 0; j < cols; j++) {
            if (mountainMap[i][j] === 0) {
                bottom = new Position(i, j, 0);
            }
            if (mountainMap[i][j] > maxHeight) {
                maxHeight = mountainMap[i][j];
                peak = new Position(i, j, 0);
            }
        }
    }
    
    // 定义四个方向
    const directions = [[-1, 0], [0, 1], [1, 0], [0, -1]];
    
    // 初始化访问数组
    const visited = Array(rows).fill().map(() => Array(cols).fill(false));
    visited[bottom.x][bottom.y] = true;
    
    // BFS队列
    const queue = [bottom];
    
    while (queue.length > 0) {
        const curr = queue.shift();
        
        // 到达山峰
        if (curr.x === peak.x && curr.y === peak.y) {
            return curr.steps;
        }
        
        // 检查四个方向
        for (const [dx, dy] of directions) {
            const newX = curr.x + dx;
            const newY = curr.y + dy;
            
            if (isValid(newX, newY, rows, cols) && !visited[newX][newY]) {
                const heightDiff = mountainMap[newX][newY] - mountainMap[curr.x][curr.y];
                
                if (Math.abs(heightDiff) <= climbAbility) {
                    visited[newX][newY] = true;
                    queue.push(new Position(newX, newY, curr.steps + 1));
                }
            }
        }
    }
    
    return -1;
}

function isValid(x, y, rows, cols) {
    return x >= 0 && x < rows && y >= 0 && y < cols;
}

// 读取输入
function main() {
    const readline = require('readline');
    const rl = readline.createInterface({
        input: process.stdin,
        output: process.stdout
    });
    
    let climbAbility, rows, cols;
    const mountainMap = [];
    let lineCount = 0;
    
    rl.on('line', (line) => {
        if (lineCount === 0) {
            climbAbility = parseInt(line);
        } else if (lineCount === 1) {
            [rows, cols] = line.split(' ').map(Number);
        } else {
            mountainMap.push(line.split(' ').map(Number));
            if (mountainMap.length === rows) {
                console.log(findShortestPath(climbAbility, mountainMap));
                rl.close();
            }
        }
        lineCount++;
    });
}

main();

 C语言

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

#define MAX_SIZE 1000

// 位置结构体
typedef struct {
    int x, y, steps;
} Position;

// 队列结构体
typedef struct {
    Position data[MAX_SIZE * MAX_SIZE];
    int front, rear;
} Queue;

// 初始化队列
void initQueue(Queue* q) {
    q->front = q->rear = 0;
}

// 入队
void enqueue(Queue* q, Position pos) {
    q->data[q->rear++] = pos;
}

// 出队
Position dequeue(Queue* q) {
    return q->data[q->front++];
}

// 判断队列是否为空
bool isEmpty(Queue* q) {
    return q->front == q->rear;
}

// 判断位置是否有效
bool isValid(int x, int y, int rows, int cols) {
    return x >= 0 && x < rows && y >= 0 && y < cols;
}

// 寻找最短路径
int findShortestPath(int climbAbility, int** mountainMap, int rows, int cols) {
    // 找到山底和山峰
    Position bottom = {0}, peak = {0};
    int maxHeight = -1;
    
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (mountainMap[i][j] == 0) {
                bottom.x = i;
                bottom.y = j;
            }
            if (mountainMap[i][j] > maxHeight) {
                maxHeight = mountainMap[i][j];
                peak.x = i;
                peak.y = j;
            }
        }
    }
    
    // 定义四个方向
    int directions[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    
    // 初始化访问数组
    bool** visited = (bool**)malloc(rows * sizeof(bool*));
    for (int i = 0; i < rows; i++) {
        visited[i] = (bool*)calloc(cols, sizeof(bool));
    }
    visited[bottom.x][bottom.y] = true;
    
    // 初始化队列
    Queue queue;
    initQueue(&queue);
    bottom.steps = 0;
    enqueue(&queue, bottom);
    
    int result = -1;
    
    while (!isEmpty(&queue)) {
        Position curr = dequeue(&queue);
        
        // 到达山峰
        if (curr.x == peak.x && curr.y == peak.y) {
            result = curr.steps;
            break;
        }
        
        // 检查四个方向
        for (int i = 0; i < 4; i++) {
            int newX = curr.x + directions[i][0];
            int newY = curr.y + directions[i][1];
            
            if (isValid(newX, newY, rows, cols) && !visited[newX][newY]) {
                int heightDiff = mountainMap[newX][newY] - mountainMap[curr.x][curr.y];
                
                if (abs(heightDiff) <= climbAbility) {
                    visited[newX][newY] = true;
                    Position next = {newX, newY, curr.steps + 1};
                    enqueue(&queue, next);
                }
            }
        }
    }
    
    // 释放内存
    for (int i = 0; i < rows; i++) {
        free(visited[i]);
    }
    free(visited);
    
    return result;
}

int main() {
    int climbAbility, rows, cols;
    scanf("%d", &climbAbility);
    scanf("%d %d", &rows, &cols);
    
    // 分配内存并读取山地图
    int** mountainMap = (int**)malloc(rows * sizeof(int*));
    for (int i = 0; i < rows; i++) {
        mountainMap[i] = (int*)malloc(cols * sizeof(int));
        for (int j = 0; j < cols; j++) {
            scanf("%d", &mountainMap[i][j]);
        }
    }
    
    // 计算并输出结果
    printf("%d\n", findShortestPath(climbAbility, mountainMap, rows, cols));
    
    // 释放内存
    for (int i = 0; i < rows; i++) {
        free(mountainMap[i]);
    }
    free(mountainMap);
    
    return 0;
}

【华为od机试真题Python+JS+Java合集】【超值优惠】：Py/JS/Java合集

【华为od机试真题Python】：Python真题题库

【华为od机试真题JavaScript】：JavaScript真题题库

【华为od机试真题Java】：Java真题题库

【华为od机试真题C++】：C++真题题库

【华为od机试真题C语言】：C语言真题题库

【华为od面试手撕代码题库】：面试手撕代码题库

【华为校招&实习机试面试交流群：1048120678】