#P3253. 周末爬山(200分)
-
1000ms
Tried: 91
Accepted: 31
Difficulty: 4
所属公司 :
华为od
周末爬山(200分)
题面描述
小塔准备在周末去爬山锻炼,山地图以二维矩阵表示,其中0代表平地,1到9表示不同的山高度。小塔每次只能向上下左右四个方向移动一格,且移动到相邻位置的高度差不能超过k。小塔从左上角的(0,0)位置出发,要求找到能够到达的最高峰的高度以及到达该峰的最短步数。如果无法到达任何山峰,则输出0 0。
思路
这道题可以通过广度优先搜索(BFS)来解决。具体步骤如下:
-
初始化:
- 使用一个
m x n的数组visited来记录每个位置是否已经被访问过,以及到达该位置的步数。 - 使用一个队列
q来进行BFS,初始时将起点(0,0)加入队列,步数为0。 - 初始化
max_height为起点的高度,min_steps为0。
- 使用一个
-
BFS过程:
- 从队列中取出当前的位置和步数。
- 检查当前的位置的高度是否大于当前记录的
max_height,如果是,则更新max_height和min_steps。如果相等且步数更少,则更新min_steps。 - 尝试向上下左右四个方向移动,检查新位置是否在地图范围内,且高度差不超过
k,且未被访问过。 - 如果满足条件,则将新位置加入队列,并标记为已访问,步数加一。
-
结束条件:
- BFS遍历完成后,输出
max_height和min_steps。如果max_height仍为起点的高度且未能移动,则输出0 0。
- BFS遍历完成后,输出
-
特殊情况处理:
- 如果起点的高度已经为
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。