题解思路

我们可以将山脉地图看成一个二维网格，每个格子代表一个节点，相邻（上、下、左、右）格子之间有边相连。由于每步移动代价相同（均为 1），并且我们要找从山底到山峰的最少步数，最合适的算法是 广度优先搜索（BFS）。

具体步骤如下：

1. 扫描地图，找到山底起点 start（高度为 0 的唯一坐标）和山峰终点 target（最高高度的唯一坐标）。
2. 初始化队列，将 start 入队，并用一个与地图同型的布尔数组 vis 记录访问状态。
3. BFS 过程：
   • 每次从队列取出当前格子 (x,y) 及其已走步数 d。
   • 枚举四个方向的新坐标 (nx,ny)，判断是否越界、未访问，并且满足高度差限制：
     • 向高处移动：grid[nx][ny] - grid[x][y] ≤ climbAbility
     • 向低处移动：grid[x][y] - grid[nx][ny] ≤ climbAbility
   • 若满足，则将 (nx,ny) 标记为已访问并入队，步数 d+1。
   • 若 (nx,ny) 为 target，即可立即返回 d+1。
4. 若 BFS 结束仍未到达山峰，返回 -1。

算法分析

• 正确性：BFS 保证第一次到达终点时所走步数即为最少步数。
• 高度限制判断：无论上坡还是下坡，实际上都可统一为 |grid[nx][ny] - grid[x][y]| ≤ climbAbility。
• 访问标记：防止重复入队，降低时间开销。

复杂度分析

• 令网格大小为 N=M行×M列，BFS 最多访问所有格子一次，每个格子检查 4 个方向。
• 时间复杂度：O(N×M)。
• 空间复杂度：O(N×M)，用于队列和访问数组。

代码实现

Python

from collections import deque

def min_steps(grid, ability):
    n, m = len(grid), len(grid[0])
    # 找起点（高度0）和终点（最高点）
    start = target = None
    max_h = -1
    for i in range(n):
        for j in range(m):
            h = grid[i][j]
            if h == 0:
                start = (i, j)
            if h > max_h:
                max_h, target = h, (i, j)
    # BFS 初始化
    vis = [[False]*m for _ in range(n)]
    q = deque()
    q.append((*start, 0))
    vis[start[0]][start[1]] = True
    # 四个方向
    dirs = [(-1,0),(1,0),(0,-1),(0,1)]
    while q:
        x, y, d = q.popleft()
        if (x, y) == target:
            return d
        for dx, dy in dirs:
            nx, ny = x+dx, y+dy
            if 0 <= nx < n and 0 <= ny < m and not vis[nx][ny]:
                diff = grid[nx][ny] - grid[x][y]
                if abs(diff) <= ability:
                    vis[nx][ny] = True
                    q.append((nx, ny, d+1))
    return -1

# 读入与输出
if __name__ == "__main__":
    ability = int(input().strip())
    n, m = map(int, input().split())
    grid = [list(map(int, input().split())) for _ in range(n)]
    print(min_steps(grid, ability))

Java

import java.util.*;

public class Solution {
    static class Node {
        int x, y, d;
        Node(int x, int y, int d) {
            this.x = x; this.y = y; this.d = d;
        }
    }

    public static int minSteps(int[][] grid, int ability) {
        int n = grid.length, m = grid[0].length;
        int sx=0, sy=0, tx=0, ty=0, maxH=-1;
        // 找起点与终点
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                int h = grid[i][j];
                if (h == 0) { sx = i; sy = j; }
                if (h > maxH) { maxH = h; tx = i; ty = j; }
            }
        }
        boolean[][] vis = new boolean[n][m];
        Queue<Node> q = new LinkedList<>();
        q.add(new Node(sx, sy, 0));
        vis[sx][sy] = true;
        int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
        while (!q.isEmpty()) {
            Node cur = q.poll();
            if (cur.x == tx && cur.y == ty) return cur.d;
            for (int[] dir : dirs) {
                int nx = cur.x + dir[0], ny = cur.y + dir[1];
                if (nx>=0 && nx<n && ny>=0 && ny<m && !vis[nx][ny]) {
                    int diff = grid[nx][ny] - grid[cur.x][cur.y];
                    if (Math.abs(diff) <= ability) {
                        vis[nx][ny] = true;
                        q.add(new Node(nx, ny, cur.d+1));
                    }
                }
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int ability = Integer.parseInt(in.nextLine().trim());
        String[] dims = in.nextLine().split(" ");
        int n = Integer.parseInt(dims[0]), m = Integer.parseInt(dims[1]);
        int[][] grid = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                grid[i][j] = in.nextInt();
            }
        }
        System.out.println(minSteps(grid, ability));
    }
}

C++

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

struct Node {
    int x, y, d;
};

int minSteps(vector<vector<int>>& grid, int ability) {
    int n = grid.size(), m = grid[0].size();
    int sx=0, sy=0, tx=0, ty=0, maxH=-1;
    // 找起点与终点
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            int h = grid[i][j];
            if (h == 0) { sx = i; sy = j; }
            if (h > maxH) { maxH = h; tx = i; ty = j; }
        }
    }
    vector<vector<bool>> vis(n, vector<bool>(m, false));
    queue<Node> q;
    q.push({sx, sy, 0});
    vis[sx][sy] = true;
    int dirs[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
    while (!q.empty()) {
        auto cur = q.front(); q.pop();
        if (cur.x == tx && cur.y == ty) return cur.d;
        for (auto &di : dirs) {
            int nx = cur.x + di[0], ny = cur.y + di[1];
            if (nx>=0 && nx<n && ny>=0 && ny<m && !vis[nx][ny]) {
                int diff = grid[nx][ny] - grid[cur.x][cur.y];
                if (abs(diff) <= ability) {
                    vis[nx][ny] = true;
                    q.push({nx, ny, cur.d+1});
                }
            }
        }
    }
    return -1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int ability;
    cin >> ability;
    int n, m;
    cin >> n >> m;
    vector<vector<int>> grid(n, vector<int>(m));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> grid[i][j];

    cout << minSteps(grid, ability) << "\n";
    return 0;
}

题目内容

给定一个二维数组$mountainMap$表示一座山的地图，数组中的每个元素$mountainMap[x][y]$代表坐标$(x,y)$处 山的高度。登山员从山底出发，爬到山峰。

山底的含义:$mountainMap$中高度为$0$的坐标点。

山峰的含义:$mountainMap$中高度最高的坐标点。

山底和山峰有且仅有一个坐标。

登山员每次移动只能从当前位置向上下左右四个方向移动一格，向高处移动时，移动到的位置的山的高度不能高于当前位置山的高度加上固定的攀爬能力值$climbAbility$;向低处移动时，移动到的位置的山的高度不能低于当前位置山的高度减去$climbAbility$。

数值取值范围:

请计算出从山底移动到山峰，最少需要移动几次?

输入描述

1.第一行为$climbAbility$的值

2.第二行为$mountainMapRows\ mountainMapCols$

3.从第三行开始为$mountainMapRows$行$mountainMapCols$列的高度二维数组 $mountainMap[mountainMapRows][mountainMapCols]$，每行的高度数字中间用空格分割

样例输入

$1$

$6\ 6$

$4\ 5\ 6\ 5\ 5\ 5$

$3\ 4\ 5\ 6\ 7\ 7$

$2\ 10\ 10\ 10\ 8\ 8$

$1\ 1\ 1\ 10\ 9\ 9$

$1\ 0\ 10\ 10\ 10\ 10$

$9\ 9\ 9\ 9\ 11\ 10$

图例：

格子中的数字代表山峰高度，$climbAbility$为$1$，最短路线如图所示。

输出描述

从山底移动到山峰，最少移动次数。

如果无法移动至山峰，则输出$-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$次

样例3

输入

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

输出

-1

说明

无法达到山峰，输出$-1$

提示

$1$.山底和山峰有且仅有一个坐标。

$2$.初始位置在山底，山底不一定在数组边缘位置，见样例$2$

$3$.山峰的高度大于$0$