题面描述

小塔准备在周末去爬山锻炼，山地图以二维矩阵表示，其中0代表平地，1到9表示不同的山高度。小塔每次只能向上下左右四个方向移动一格，且移动到相邻位置的高度差不能超过k。小塔从左上角的$(0,0)$位置出发，要求找到能够到达的最高峰的高度以及到达该峰的最短步数。如果无法到达任何山峰，则输出0 0。

思路

这道题可以通过广度优先搜索（BFS）来解决。具体步骤如下：

1. 初始化：

   • 使用一个m x n的数组visited来记录每个位置是否已经被访问过，以及到达该位置的步数。
   • 使用一个队列q来进行BFS，初始时将起点$(0,0)$加入队列，步数为0。
   • 初始化max_height为起点的高度，min_steps为0。

2. BFS过程：

   • 从队列中取出当前的位置和步数。
   • 检查当前的位置的高度是否大于当前记录的max_height，如果是，则更新max_height和min_steps。如果相等且步数更少，则更新min_steps。
   • 尝试向上下左右四个方向移动，检查新位置是否在地图范围内，且高度差不超过k，且未被访问过。
   • 如果满足条件，则将新位置加入队列，并标记为已访问，步数加一。

3. 结束条件：

   • BFS遍历完成后，输出max_height和min_steps。如果max_height仍为起点的高度且未能移动，则输出0 0。

4. 特殊情况处理：

   • 如果起点的高度已经为0且无法移动到任何其他位置，则直接输出0 0。

代码分析

• 数据结构选择：

  • 使用二维数组map存储山地图的高度信息。
  • 使用二维数组visited记录每个位置是否已被访问，以及到达该位置的最短步数。
  • 使用队列q来实现BFS。

• 算法步骤：

  • 从起点$(0,0)$开始，进行BFS遍历。
  • 在遍历过程中，实时更新能够到达的最高峰的高度及其对应的最短步数。
  • BFS保证了每个位置第一次被访问时就是以最短步数到达的，因此无需重复访问。

• 时间复杂度：

  • 最坏情况下，需要遍历整个地图，时间复杂度为O(m * n)，在题目给定的范围内是可行的。

• 空间复杂度：

  • 需要存储m x n的map和visited数组，空间复杂度为O(m * n)，在题目给定的范围内也是可接受的。

cpp

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

int main(){
    // 关闭同步，加快I/O速度
    ios::sync_with_stdio(false);
    cin.tie(0);

    int m, n, k;
    // 输入行数m，列数n，以及每次移动允许的最大高度差k
    cin >> m >> n >> k;

    // 初始化山地图，m行n列
    vector<vector<int>> map(m, vector<int>(n));
    for(auto &row : map){
        for(auto &cell : row){
            cin >> cell; // 输入每个位置的高度
        }
    }

    // 定义四个方向的移动：上、下、左、右
    int dx[4] = {-1, 1, 0, 0};
    int dy[4] = {0, 0, -1, 1};

    // 初始化访问数组，记录每个位置是否被访问过以及到达该位置的步数
    // 初始值为-1，表示未访问
    vector<vector<int>> visited(m, vector<int>(n, -1));

    // 使用队列进行广度优先搜索（BFS）
    queue<pair<int, int>> q;

    // 将起点(0,0)加入队列，并标记为已访问，步数为0
    q.push({0, 0});
    visited[0][0] = 0;

    // 初始化记录最高峰的高度和到达该峰的最短步数
    int max_height = map[0][0];
    int min_steps = 0;

    // BFS遍历
    while(!q.empty()){
        pair<int, int> current = q.front(); // 当前的位置
        q.pop();
        int x = current.first;
        int y = current.second;
        int steps = visited[x][y]; // 到达当前点的步数

        // 更新最高峰的高度和最短步数
        if(map[x][y] > max_height){
            max_height = map[x][y];
            min_steps = steps;
        }
        else if(map[x][y] == max_height && steps < min_steps){
            min_steps = steps;
        }

        // 尝试向四个方向移动
        for(int dir=0; dir<4; dir++){
            int nx = x + dx[dir];
            int ny = y + dy[dir];

            // 检查新位置是否在地图范围内，且未被访问过
            if(nx >=0 && nx < m && ny >=0 && ny < n && visited[nx][ny]==-1){
                // 检查高度差是否在允许范围内
                if(abs(map[nx][ny] - map[x][y]) <= k){
                    visited[nx][ny] = steps +1; // 标记为已访问，并记录步数
                    q.push({nx, ny}); // 将新位置加入队列
                }
            }
        }
    }

    // 判断是否找到可到达的峰
    // 如果最高峰高度大于0，并且不是仅停留在起点
    if(max_height > 0 && !(max_height == map[0][0] && min_steps ==0)){
        cout << max_height << " " << min_steps;
    }
    else{
        // 如果起点本身就是一个峰
        if(map[0][0] >0){
            cout << map[0][0] << " " << 0;
        }
        else{
            // 无法到达任何峰
            cout << "0 0";
        }
    }
}

python

from collections import deque

def main():
    # 输入行数m，列数n，以及每次移动允许的最大高度差k
    m, n, k = map(int, input().split())
    
    # 初始化山地图，m行n列
    mountain_map = []
    for _ in range(m):
        row = list(map(int, input().split()))
        mountain_map.append(row)
    
    # 定义四个方向的移动：上、下、左、右
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    
    # 初始化访问数组，记录每个位置是否被访问过以及到达该位置的步数
    visited = [[-1] * n for _ in range(m)]
    
    # 使用队列进行广度优先搜索（BFS）
    q = deque()
    
    # 将起点(0,0)加入队列，并标记为已访问，步数为0
    q.append((0, 0))
    visited[0][0] = 0
    
    # 初始化记录最高峰的高度和到达该峰的最短步数
    max_height = mountain_map[0][0]
    min_steps = 0
    
    # BFS遍历
    while q:
        x, y = q.popleft()  # 当前的位置
        steps = visited[x][y]  # 到达当前点的步数
        
        # 更新最高峰的高度和最短步数
        if mountain_map[x][y] > max_height:
            max_height = mountain_map[x][y]
            min_steps = steps
        elif mountain_map[x][y] == max_height and steps < min_steps:
            min_steps = steps
        
        # 尝试向四个方向移动
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            
            # 检查新位置是否在地图范围内，且未被访问过
            if 0 <= nx < m and 0 <= ny < n and visited[nx][ny] == -1:
                # 检查高度差是否在允许范围内
                if abs(mountain_map[nx][ny] - mountain_map[x][y]) <= k:
                    visited[nx][ny] = steps + 1  # 标记为已访问，并记录步数
                    q.append((nx, ny))  # 将新位置加入队列
    
    # 判断是否找到可到达的峰
    if max_height > 0 and not (max_height == mountain_map[0][0] and min_steps == 0):
        print(max_height, min_steps)
    else:
        # 如果起点本身就是一个峰
        if mountain_map[0][0] > 0:
            print(mountain_map[0][0], 0)
        else:
            print("0 0")

# 调用主函数
if __name__ == "__main__":
    main()

java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 输入行数m，列数n，以及每次移动允许的最大高度差k
        int m = scanner.nextInt();
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        
        // 初始化山地图，m行n列
        int[][] mountainMap = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                mountainMap[i][j] = scanner.nextInt();
            }
        }
        
        // 定义四个方向的移动：上、下、左、右
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        
        // 初始化访问数组，记录每个位置是否被访问过以及到达该位置的步数
        int[][] visited = new int[m][n];
        for (int[] row : visited) {
            Arrays.fill(row, -1); // 初始值为-1，表示未访问
        }
        
        // 使用队列进行广度优先搜索（BFS）
        Queue<int[]> queue = new LinkedList<>();
        
        // 将起点(0,0)加入队列，并标记为已访问，步数为0
        queue.offer(new int[]{0, 0});
        visited[0][0] = 0;
        
        // 初始化记录最高峰的高度和到达该峰的最短步数
        int maxHeight = mountainMap[0][0];
        int minSteps = 0;
        
        // BFS遍历
        while (!queue.isEmpty()) {
            int[] current = queue.poll(); // 当前的位置
            int x = current[0];
            int y = current[1];
            int steps = visited[x][y]; // 到达当前点的步数
            
            // 更新最高峰的高度和最短步数
            if (mountainMap[x][y] > maxHeight) {
                maxHeight = mountainMap[x][y];
                minSteps = steps;
            } else if (mountainMap[x][y] == maxHeight && steps < minSteps) {
                minSteps = steps;
            }
            
            // 尝试向四个方向移动
            for (int[] dir : directions) {
                int nx = x + dir[0];
                int ny = y + dir[1];
                
                // 检查新位置是否在地图范围内，且未被访问过
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && visited[nx][ny] == -1) {
                    // 检查高度差是否在允许范围内
                    if (Math.abs(mountainMap[nx][ny] - mountainMap[x][y]) <= k) {
                        visited[nx][ny] = steps + 1; // 标记为已访问，并记录步数
                        queue.offer(new int[]{nx, ny}); // 将新位置加入队列
                    }
                }
            }
        }
        
        // 判断是否找到可到达的峰
        if (maxHeight > 0 && !(maxHeight == mountainMap[0][0] && minSteps == 0)) {
            System.out.println(maxHeight + " " + minSteps);
        } else {
            // 如果起点本身就是一个峰
            if (mountainMap[0][0] > 0) {
                System.out.println(mountainMap[0][0] + " 0");
            } else {
                System.out.println("0 0");
            }
        }
        
        scanner.close(); // 关闭输入流
    }
}

题目内容

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