刷题笔记合集🔗

周末爬山

问题描述

K小姐准备在周末去爬山锻炼。山地图用二维数组表示，其中 0 代表平地，1 到 9 表示山的高度。K小姐每次爬山或下山时，高度差不能超过 。他每次只能向上、下、左、右四个方向之一移动一格。K小姐从左上角 位置出发，请计算他能爬到的最高峰高度以及到达该高峰的最短步数。

输入格式

第一行输入三个整数 、 和 ，以空格分隔。

接下来 行，每行包含 个整数（以空格分隔），表示 的二维山地图。

输出格式

输出两个整数，以空格分隔。第一个整数表示K小姐能爬到的最高峰高度，第二个整数表示到达该最高峰的最短步数。

如果存在多个相同高度的最高峰，输出步数较短的那个。

如果没有可以爬的更高的山峰，则高度和步数都输出 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

样例输出1

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

样例输出2

0 0

样例解释

样例1	根据山地图可知，能爬到的最高峰在 位置，高度为 2，最短路径为 ，最短步数为 2。
样例2	根据山地图可知，每次爬山高度差限制为 3，无法爬到任何更高的山峰，因此高度和步数都返回 0。

数据范围

题解

BFS

解题思路如下：

1. 从起点 开始，将其加入队列。
2. 每次从队列中取出一个位置，检查它的四个相邻位置。
3. 对于每个相邻位置，如果高度差不超过 ，且没有被访问过，就将其加入队列。
4. 在这个过程中，记录到达的最大高度和对应的步数。
5. 重复步骤 2-4，直到队列为空。

关键点：

• 使用一个二维数组 visited 来记录每个位置是否被访问过，避免重复访问。
• 使用一个队列来存储待访问的位置，保证按照距离起点的远近顺序访问。
• 每次访问新位置时，检查是否更新最大高度和步数。

时间复杂度分析：

• 在最坏情况下，需要访问地图上的每个位置一次，时间复杂度为 。
• 对于给定的数据范围（），这个复杂度是可以接受的。

参考代码

• Python

from collections import deque

def climb_mountain(m, n, k, mountain):
    # 定义四个方向：上、下、左、右
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    
    # 初始化访问数组和队列
    visited = [[False] * n for _ in range(m)]
    queue = deque([(0, 0, 0)])  # (x, y, steps)
    visited[0][0] = True
    
    max_height = mountain[0][0]
    min_steps = 0
    
    while queue:
        x, y, steps = queue.popleft()
        
        # 检查是否需要更新最大高度和最短步数
        if mountain[x][y] > max_height or (mountain[x][y] == max_height and steps < min_steps):
            max_height = mountain[x][y]
            min_steps = steps
        
        # 检查四个方向
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            
            # 检查新位置是否在地图范围内且未被访问过
            if 0 <= nx < m and 0 <= ny < n and not visited[nx][ny]:
                # 检查高度差是否在允许范围内
                if abs(mountain[nx][ny] - mountain[x][y]) <= k:
                    queue.append((nx, ny, steps + 1))
                    visited[nx][ny] = True
    
    # 如果没有爬到更高的山峰，返回0 0
    return (max_height, min_steps) if max_height > mountain[0][0] else (0, 0)

# 读取输入
m, n, k = map(int, input().split())
mountain = [list(map(int, input().split())) for _ in range(m)]

# 计算结果并输出
height, steps = climb_mountain(m, n, k, mountain)
print(f"{height} {steps}")

• C

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

#define MAX_SIZE 500

// 定义队列节点结构
typedef struct {
    int x, y, steps;
} Node;

// 定义队列结构
typedef struct {
    Node* data;
    int front, rear, size;
} Queue;

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

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

// 出队
Node dequeue(Queue* queue) {
    queue->front = (queue->front + 1) % (MAX_SIZE * MAX_SIZE);
    queue->size--;
    return queue->data[queue->front];
}

// 判断队列是否为空
bool isEmpty(Queue* queue) {
    return queue->size == 0;
}

// 主函数
int main() {
    int m, n, k;
    scanf("%d %d %d", &m, &n, &k);
    
    int mountain[MAX_SIZE][MAX_SIZE];
    bool visited[MAX_SIZE][MAX_SIZE] = {false};
    
    // 读取山地图
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &mountain[i][j]);
        }
    }
    
    int directions[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    Queue* queue = createQueue(MAX_SIZE * MAX_SIZE);
    
    int max_height = mountain[0][0];
    int min_steps = 0;
    
    enqueue(queue, 0, 0, 0);
    visited[0][0] = true;
    
    while (!isEmpty(queue)) {
        Node current = dequeue(queue);
        int x = current.x, y = current.y, steps = current.steps;
        
        // 更新最大高度和最短步数
        if (mountain[x][y] > max_height || (mountain[x][y] == max_height && steps < min_steps)) {
            max_height = mountain[x][y];
            min_steps = steps;
        }
        
        // 检查四个方向
        for (int i = 0; i < 4; i++) {
            int nx = x + directions[i][0];
            int ny = y + directions[i][1];
            
            if (nx >= 0 && nx < m && ny >= 0 && ny < n && !visited[nx][ny]) {
                if (abs(mountain[nx][ny] - mountain[x][y]) <= k) {
                    enqueue(queue, nx, ny, steps + 1);