当前位置：首页 > news >正文

华为OD机试 - 周末爬山 - 广度优先搜索BFS（Python/JS/C/C++ 2024 E卷 200分）

news 2025/7/4 15:14:02

在这里插入图片描述

华为OD机试 2024E卷题库疯狂收录中，刷题点这里

专栏导读

本专栏收录于《华为OD机试真题（Python/JS/C/C++）》。

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。

一、题目描述

周末小明准备去爬山锻炼，0代表平地，山的高度使用1到9来表示，小明每次爬山或下山高度只能相差k及k以内，每次只能上下左右一个方向上移动一格，小明从左上角(0,0)位置出发

二、输入描述

第一行输入n m k(空格分隔)

代表n*m的二维山地图，k为小明每次爬山或下山高度差的最大值，然后接下来输入山地图，一共m行n列，均以空格分隔。取值范围：

0 < m <= 500
0 < n <= 500
0 < k <= 5

备注

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

三、输出描述

请问小明能爬到的最高峰是多少，到该最高峰的最短步数，输出以空格分隔。

同高度的山峰输出较小步数。

如果没有可以爬的山峰，则高度和步数均返回0

四、测试用例

测试用例1：

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 2

3、说明

根据山地图可知，能爬到的最高峰在(0,2)位置，高度为2，最短路径为(0,0)-(0,1)-(0,2)，最短步数为2。

测试用例2：

1、输入

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

3、说明

根据山地图可知，每次爬山距离3，无法爬到山峰上，步数为0。

五、解题思路

本题是一个典型的二维网格搜索问题。小明从地图的左上角(0, 0)出发，每次只能上下左右移动一格，爬山或下山的高度差不能超过k。那么这就是一个 广度优先搜索（BFS） 问题，我们可以使用BFS遍历整个地图，记录每个位置的最短步数和能达到的最高峰值。

具体步骤如下：

初始化：从起点(0, 0)开始，将其加入队列，同时记录步数。
BFS搜索：利用队列每次取出当前位置，尝试向上下左右四个方向移动，判断是否可以移动。如果可以移动，则记录该位置的步数并加入队列。
高度条件判断：每次移动时需要判断目标位置的高度与当前高度差是否在k的范围内。
结果记录：在遍历过程中记录最高峰及其最短步数，最终输出结果。如果没有可爬的山峰，则输出高度和步数均为0。

六、Python算法源码

from collections import deque# 定义四个方向：上、下、左、右
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]def bfs(map, m, n, k):# 队列用于BFS存储 [x坐标, y坐标, 当前步数]queue = deque()visited = [[False] * n for _ in range(m)]  # 记录访问过的位置queue.append((0, 0, 0))  # 从左上角(0, 0)出发，步数为0visited[0][0] = Truemax_height = map[0][0]  # 最高峰高度min_steps = 0  # 最短步数while queue:x, y, steps = queue.popleft()# 尝试四个方向移动for i in range(4):new_x = x + dx[i]new_y = y + dy[i]# 判断新位置是否在地图范围内if 0 <= new_x < m and 0 <= new_y < n and not visited[new_x][new_y]:# 判断高度差是否符合条件if abs(map[new_x][new_y] - map[x][y]) <= k:visited[new_x][new_y] = Truequeue.append((new_x, new_y, steps + 1))# 更新最高峰和最短步数if map[new_x][new_y] > max_height:max_height = map[new_x][new_y]min_steps = steps + 1elif map[new_x][new_y] == max_height and (steps + 1) < min_steps:min_steps = steps + 1# 如果最高峰和起点相同（即无法爬山），返回高度和步数为0if max_height == map[0][0]:return [0, 0]return [max_height, min_steps]# 主函数
def main():# 输入 n, m, kn, m, k = map(int, input().split())# 输入山地图mountain_map = []for i in range(m):row = list(map(int, input().split()))mountain_map.append(row)# 调用BFS方法寻找最高峰和最短步数result = bfs(mountain_map, m, n, k)# 输出结果print(result[0], result[1])# 调用主函数
if __name__ == "__main__":main()

七、JavaScript算法源码

function bfs(map, m, n, k) {// 定义四个方向：上、下、左、右const dx = [-1, 1, 0, 0];const dy = [0, 0, -1, 1];// 队列用于BFS存储 [x坐标, y坐标, 当前步数]let queue = [];let visited = Array.from({ length: m }, () => Array(n).fill(false)); // 记录是否访问过的点queue.push([0, 0, 0]); // 从左上角(0,0)出发，步数为0visited[0][0] = true;let maxHeight = map[0][0]; // 最高峰高度let minSteps = 0;          // 最短步数while (queue.length > 0) {let [x, y, steps] = queue.shift(); // 取出队列的第一个元素// 尝试四个方向移动for (let i = 0; i < 4; i++) {let newX = x + dx[i];let newY = y + dy[i];// 判断新位置是否在地图范围内if (newX >= 0 && newX < m && newY >= 0 && newY < n && !visited[newX][newY]) {// 判断高度差是否符合条件if (Math.abs(map[newX][newY] - map[x][y]) <= k) {visited[newX][newY] = true;queue.push([newX, newY, steps + 1]);// 更新最高峰和最短步数if (map[newX][newY] > maxHeight) {maxHeight = map[newX][newY];minSteps = steps + 1;} else if (map[newX][newY] === maxHeight && (steps + 1) < minSteps) {minSteps = steps + 1;}}}}}// 如果最高峰和起点相同（即无法爬山），返回高度和步数为0if (maxHeight === map[0][0]) {return [0, 0];}return [maxHeight, minSteps];
}// 主函数
function main() {const input = require('readline-sync');// 输入 n, m, klet [n, m, k] = input.question("Enter n, m, k: ").split(' ').map(Number);// 输入山地图let map = [];console.log(`Enter the map data (${m} rows of ${n} columns):`);for (let i = 0; i < m; i++) {map.push(input.question().split(' ').map(Number));}// 调用BFS方法寻找最高峰和最短步数let result = bfs(map, m, n, k);// 输出结果console.log(`${result[0]} ${result[1]}`);
}// 调用主函数
main();

八、C算法源码

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>#define MAX 500// 定义四个方向：上、下、左、右
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};// 定义队列结构体
typedef struct {int x, y, steps;
} QueueNode;typedef struct {QueueNode data[MAX * MAX];int front, rear;
} Queue;// 初始化队列
void initQueue(Queue *q) {q->front = 0;q->rear = 0;
}// 队列是否为空
bool isEmpty(Queue *q) {return q->front == q->rear;
}// 入队
void enqueue(Queue *q, int x, int y, int steps) {q->data[q->rear].x = x;q->data[q->rear].y = y;q->data[q->rear].steps = steps;q->rear++;
}// 出队
QueueNode dequeue(Queue *q) {return q->data[q->front++];
}// 广度优先搜索（BFS）算法
void bfs(int map[MAX][MAX], int m, int n, int k, int *maxHeight, int *minSteps) {// 初始化队列和访问标记数组Queue queue;bool visited[MAX][MAX] = {false};initQueue(&queue);enqueue(&queue, 0, 0, 0); // 从左上角(0, 0)出发，步数为0visited[0][0] = true;*maxHeight = map[0][0]; // 最高峰高度*minSteps = 0;          // 最短步数// BFS遍历while (!isEmpty(&queue)) {QueueNode current = dequeue(&queue);int x = current.x;int y = current.y;int steps = current.steps;// 尝试向四个方向移动for (int i = 0; i < 4; i++) {int newX = x + dx[i];int newY = y + dy[i];// 判断新位置是否在地图范围内if (newX >= 0 && newX < m && newY >= 0 && newY < n && !visited[newX][newY]) {// 判断高度差是否符合条件if (abs(map[newX][newY] - map[x][y]) <= k) {visited[newX][newY] = true;enqueue(&queue, newX, newY, steps + 1);// 更新最高峰和最短步数if (map[newX][newY] > *maxHeight) {*maxHeight = map[newX][newY];*minSteps = steps + 1;} else if (map[newX][newY] == *maxHeight && (steps + 1) < *minSteps) {*minSteps = steps + 1;}}}}}// 如果最高峰和起点相同，返回高度和步数为0if (*maxHeight == map[0][0]) {*maxHeight = 0;*minSteps = 0;}
}int main() {int n, m, k;// 输入 n, m, kprintf("Enter n, m, k: ");scanf("%d %d %d", &n, &m, &k);int map[MAX][MAX];// 输入山地图printf("Enter the map data (%d rows of %d columns):\n", m, n);for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {scanf("%d", &map[i][j]);}}int maxHeight, minSteps;// 调用BFS方法寻找最高峰和最短步数bfs(map, m, n, k, &maxHeight, &minSteps);// 输出结果printf("%d %d\n", maxHeight, minSteps);return 0;
}

九、C++算法源码

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
using namespace std;// 定义方向：上、下、左、右
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};// BFS算法
pair<int, int> bfs(vector<vector<int>>& map, int m, int n, int k) {// 队列，用于BFS存储 [x坐标, y坐标, 当前步数]queue<pair<pair<int, int>, int>> q;vector<vector<bool>> visited(m, vector<bool>(n, false));  // 记录访问过的点q.push({{0, 0}, 0});  // 从左上角(0,0)出发，步数为0visited[0][0] = true;int maxHeight = map[0][0];  // 最高峰高度int minSteps = 0;           // 最短步数while (!q.empty()) {auto current = q.front();q.pop();int x = current.first.first;int y = current.first.second;int steps = current.second;// 尝试向四个方向移动for (int i = 0; i < 4; i++) {int newX = x + dx[i];int newY = y + dy[i];// 检查新位置是否在地图范围内if (newX >= 0 && newX < m && newY >= 0 && newY < n && !visited[newX][newY]) {// 判断高度差是否符合条件if (abs(map[newX][newY] - map[x][y]) <= k) {visited[newX][newY] = true;q.push({{newX, newY}, steps + 1});// 更新最高峰和最短步数if (map[newX][newY] > maxHeight) {maxHeight = map[newX][newY];minSteps = steps + 1;} else if (map[newX][newY] == maxHeight && (steps + 1) < minSteps) {minSteps = steps + 1;}}}}}// 如果最高峰和起点相同，返回高度和步数为0if (maxHeight == map[0][0]) {return {0, 0};}return {maxHeight, minSteps};
}int main() {int n, m, k;// 输入 n, m, kcout << "Enter n, m, k: ";cin >> n >> m >> k;vector<vector<int>> map(m, vector<int>(n));// 输入山地图cout << "Enter the map data (" << m << " rows of " << n << " columns):" << endl;for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {cin >> map[i][j];}}// 调用BFS方法寻找最高峰和最短步数pair<int, int> result = bfs(map, m, n, k);// 输出结果cout << result.first << " " << result.second << endl;return 0;
}