(B卷,200分)- 周末爬山（Java & JS & Python & C）

题目描述

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

备注

所有用例输入均为正确格式，且在取值范围内，考生不需要考虑不合法的输入格式。

用例

题目解析

本题可以使用广度优先搜索进行解题。

初始时，小明位于(0, 0)位置，此时走的步数step = 0，假设地图为matrix，则到高度matrix[0][0]的最短步数为step=0。

我们可以假设，爬山的最大高度为maxHeight，到达此高度的最小步数为minStep，则初始时，maxHeight = maxtrix[0][0]，minStep = 0。

对于任意当前位置(x, y)，假设其下一步位置是(newX, newY)

本题需要注意的是：向四个方向进行深搜时，需要注意当前位置的高度值，和下一个位置的高度值，之间的差值需要小于等于k，才能进入下一个位置继续广搜。

如果可以进入下一步，则step++，假设(newX, newY)位置的山高度为curHeight, 则：

• 如果 curHeight > maxHeight 的话，则爬到了更高的山，此时直接更新 maxHeight = curHeight，minStep = step；
• 如果 curHeight == maxHeight 的话，则需要继续比较step和minStep，我们需要保留step和minStep中较小步数作为 maxHeight（==curHeight）山高度的步数。
• 如果 curHeight < maxHeight 的话，则无需处理

在广搜过程，为了避免走回头路，我们应该记录走过的节点，我们可以定义一个visited数组来标记走过的路。

关于广搜的原理，大家可以看：

2023.11.2

输出描述中说：如果没有可以爬的山峰，则高度和步数都返回0。

其中“没有可以爬的山峰”，结合用例2来理解的话，应该是没有可爬的更高的山峰。即当只有可爬平级的山峰，也要高度和步数都返回0。

Java算法源码

import java.util.LinkedList;
import java.util.Scanner;

public class Main {
  static int m;
  static int n;
  static int k;
  static int[][] matrix;
  static int[][] offsets = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

  static int maxHeight;
  static int minStep;

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

    m = sc.nextInt();
    n = sc.nextInt();
    k = sc.nextInt();

    matrix = new int[m][n];
    for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
        matrix[i][j] = sc.nextInt();
      }
    }

    System.out.println(getResult());
  }

  public static String getResult() {
    // 到达matrix[0][0]高度的山峰，最短步数是0
    maxHeight = matrix[0][0];
    minStep = 0;

    // 广搜
    bfs();

    if (minStep == 0) {
      // 输出描述：如果没有可以爬的山峰，则高度和步数都返回0。
      return "0 0";
    } else {
      return maxHeight + " " + minStep;
    }
  }

  public static void bfs() {
    // 广搜队列
    LinkedList<int[]> queue = new LinkedList<>();
    // 访问记录
    boolean[][] visited = new boolean[m][n];

    // 首先是(0,0)位置进入队列，且被标记为访问过
    queue.add(new int[] {0, 0});
    visited[0][0] = true;

    // 此时消耗步数为0
    int step = 0;

    while (queue.size() > 0) {
      // 这里没有用queue.removeFirst来控制广搜，而是使用newQueue来控制广搜，因为这样更方便操作step
      LinkedList<int[]> newQueue = new LinkedList<>();
      step++;

      // 遍历同一层的所有节点
      for (int[] lastPos : queue) {
        int x = lastPos[0];
        int y = lastPos[1];

        int lastHeight = matrix[x][y];

        // 四个方向位置
        for (int[] offset : offsets) {
          int newX = x + offset[0];
          int newY = y + offset[1];

          // 新位置越界则无法继续广搜
          if (newX < 0 || newX >= m || newY < 0 || newY >= n) continue;

          // 新位置已访问过，则无需重复广搜
          if (visited[newX][newY]) continue;

          int curHeight = matrix[newX][newY];

          // 前后位置高度差在k以内, 则可以进入新位置
          if (Math.abs(curHeight - lastHeight) <= k) {
            // 标记新位置已访问
            visited[newX][newY] = true;

            // 如果此时到达新位置高度的步数step更小，则更新对应高度的最小步数
            if (curHeight > maxHeight || (curHeight == maxHeight && step < minStep)) {
              maxHeight = curHeight;
              minStep = step;
            }

            // 新位置加入下一层广搜队列
            newQueue.add(new int[] {newX, newY});
          }
        }
      }

      queue = newQueue;
    }
  }
}

JS算法源码

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void (async function () {
  // Write your code here
  const [m, n, k] = (await readline()).split(" ").map(Number);

  const matrix = [];
  for (let i = 0; i < m; i++) {
    matrix.push((await readline()).split(" ").map(Number));
  }

  const offsets = [
    [-1, 0],
    [1, 0],
    [0, -1],
    [0, 1],
  ];

  // 到达matrix[0][0]高度的山峰，最短步数是0
  let maxHeight = matrix[0][0];
  let minStep = 0;

  // 广搜
  bfs();

  if (minStep == 0) {
    // 输出描述：如果没有可以爬的山峰，则高度和步数都返回0。
    console.log("0 0");
  } else {
    console.log(maxHeight + " " + minStep);
  }

  function bfs() {
    // 广搜队列
    let queue = [];
    // 访问记录
    const visited = new Array(m).fill(0).map(() => new Array(n).fill(false));

    // 首先是(0,0)位置进入队列，且被标记为访问过
    queue.push([0, 0]);
    visited[0][0] = true;

    // 此时消耗步数为0
    let step = 0;

    while (queue.length > 0) {
      // 这里没有用queue.removeFirst来控制广搜，而是使用newQueue来控制广搜，因为这样更方便操作step
      const newQueue = [];
      step++;

      // 遍历同一层的所有节点
      for (let [x, y] of queue) {
        const lastHeight = matrix[x][y];

        // 四个方向位置
        for (let [offsetX, offsetY] of offsets) {
          const newX = x + offsetX;
          const newY = y + offsetY;

          // 新位置越界则无法继续广搜
          if (newX < 0 || newX >= m || newY < 0 || newY >= n) continue;

          // 新位置已访问过，则无需重复广搜
          if (visited[newX][newY]) continue;

          const curHeight = matrix[newX][newY];

          // 前后位置高度差在k以内, 则可以进入新位置
          if (Math.abs(curHeight - lastHeight) <= k) {
            // 标记新位置已访问
            visited[newX][newY] = true;

            // 如果此时到达新位置高度的步数step更小，则更新对应高度的最小步数
            if (
              curHeight > maxHeight ||
              (curHeight == maxHeight && step < minStep)
            ) {
              maxHeight = curHeight;
              minStep = step;
            }

            // 新位置加入下一层广搜队列
            newQueue.push([newX, newY]);
          }
        }
      }

      queue = newQueue;
    }
  }
})();

Python算法源码

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

offsets = ((-1, 0), (1, 0), (0, -1), (0, 1))

# 到达matrix[0][0]高度的山峰，最短步数是0
maxHeight = matrix[0][0]
minStep = 0


def bfs():
    global maxHeight, minStep

    # 广搜队列
    queue = []
    # 访问记录
    visited = [[False] * n for _ in range(m)]

    # 首先是(0,0)位置进入队列，且被标记为访问过
    queue.append((0, 0))
    visited[0][0] = True

    # 此时消耗步数为0
    step = 0

    while len(queue) > 0:
        # 这里没有用queue.removeFirst来控制广搜，而是使用newQueue来控制广搜，因为这样更方便操作step
        newQueue = []
        step += 1

        # 遍历同一层的所有节点
        for x, y in queue:
            lastHeight = matrix[x][y]

            # 四个方向位置
            for offsetX, offsetY in offsets:
                newX = x + offsetX
                newY = y + offsetY

                # 新位置越界则无法继续广搜
                if newX < 0 or newX >= m or newY < 0 or newY >= n:
                    continue

                # 新位置已访问过，则无需重复广搜
                if visited[newX][newY]:
                    continue

                curHeight = matrix[newX][newY]

                # 前后位置高度差在k以内, 则可以进入新位置
                if abs(curHeight - lastHeight) <= k:
                    visited[newX][newY] = True

                    # 如果此时到达新位置高度的步数step更小，则更新对应高度的最小步数
                    if curHeight > maxHeight or (curHeight == maxHeight and step < minStep):
                        maxHeight = curHeight
                        minStep = step

                    # 新位置加入下一层广搜队列
                    newQueue.append((newX, newY))

        queue = newQueue


# 算法入口
def getResult():
    # 广搜
    bfs()

    if minStep == 0:
        # 输出描述：如果没有可以爬的山峰，则高度和步数都返回0。
        return "0 0"
    else:
        return f"{maxHeight} {minStep}"


# 算法调用
print(getResult())

C算法源码

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

#define MAX_SIZE 500

typedef struct ListNode {
    int ele;
    struct ListNode *prev;
    struct ListNode *next;
} ListNode;

typedef struct {
    int size;
    ListNode *head;
    ListNode *tail;
} LinkedList;

LinkedList *new_LinkedList();

void addLast_LinkedList(LinkedList *link, int ele);

int m, n, k;
int matrix[MAX_SIZE][MAX_SIZE] = {0};
int visited[MAX_SIZE][MAX_SIZE] = {0};
int offsets[4][2] = {{-1, 0},
                     {1,  0},
                     {0,  -1},
                     {0,  1}};

int maxHeight;
int minStep;

int getResult();

void bfs();

int main() {
    scanf("%d %d %d", &m, &n, &k);

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &matrix[i][j]);
        }
    }

    // 到达matrix[0][0]高度的山峰，最短步数是0
    maxHeight = matrix[0][0];
    minStep = 0;

    // 广搜
    bfs();

    if (minStep == 0) {
        // 输出描述：如果没有可以爬的山峰，则高度和步数都返回0。
        puts("0 0");
    } else {
        printf("%d %d", maxHeight, minStep);
    }

    return 0;
}

void bfs() {
    // 广搜队列
    LinkedList *queue = new_LinkedList();

    // 首先是(0,0)位置进入队列，且被标记为访问过
    addLast_LinkedList(queue, 0 * n + 0);
    visited[0][0] = 1;

    // 此时消耗步数为0
    int step = 0;

    while (queue->size > 0) {
        // 这里没有用queue.removeFirst来控制广搜，而是使用newQueue来控制广搜，因为这样更方便操作step
        LinkedList *newQueue = new_LinkedList();
        step++;

        // 遍历同一层的所有节点
        ListNode *cur = queue->head;
        while (cur != NULL) {
            int x = cur->ele / n;
            int y = cur->ele % n;

            int lastHeight = matrix[x][y];

            // 四个方向位置
            for (int i = 0; i < 4; i++) {
                int newX = x + offsets[i][0];
                int newY = y + offsets[i][1];

                // 新位置越界则无法继续广搜
                if (newX < 0 || newX >= m || newY < 0 || newY >= n) continue;

                // 新位置已访问过，则无需重复广搜
                if (visited[newX][newY]) continue;

                // 前后位置高度差在k以内, 则可以进入新位置
                int curHeight = matrix[newX][newY];

                if (abs(curHeight - lastHeight) <= k) {
                    // 标记新位置已访问
                    visited[newX][newY] = 1;

                    // 如果此时到达新位置高度的步数step更小，则更新对应高度的最小步数
                    if (curHeight > maxHeight || (curHeight == maxHeight && step < minStep)) {
                        maxHeight = curHeight;
                        minStep = step;
                    }

                    // 新位置加入下一层广搜队列
                    addLast_LinkedList(newQueue, newX * n + newY);
                }
            }

            cur = cur->next;
        }

        queue = newQueue;
    }
}


LinkedList *new_LinkedList() {
    LinkedList *link = (LinkedList *) malloc(sizeof(LinkedList));

    link->size = 0;
    link->head = NULL;
    link->tail = NULL;

    return link;
}

void addLast_LinkedList(LinkedList *link, int ele) {
    ListNode *node = (ListNode *) malloc(sizeof(ListNode));

    node->ele = ele;
    node->prev = NULL;
    node->next = NULL;

    if (link->size == 0) {
        link->head = node;
        link->tail = node;
    } else {
        link->tail->next = node;
        node->prev = link->tail;
        link->tail = node;
    }

    link->size++;
}