AlgoMooc
你已开通华为OD训练营权益,还差最后一步——完成入营激活(兑换课程 + 加飞书 + 登记服务群),即可解锁全部课程与专属服务。去激活 →
← 返回题库

P3708. 周末爬山

中等通过率 46% · 提交 1,024 · 通过 474
BFS图论矩阵

小慕正在规划一次户外徒步活动。地图用一个 n 行 m 列的网格表示,0 代表平地,1 到 9 代表不同高度的山丘。小慕每次移动只能从一个格子走到上下左右相邻的格子,且移动前后两个位置的高度差不能超过 k。小慕从地图的左上角 (0, 0) 出发,请帮她计算她能够到达的所有格子总数。

提示:带虚线的词点一下有通俗解释。

输入描述

<p> 第一行输入m n k(空格分隔) </p> <p> 代表 m*n 的二维山地图,k为小明每次爬山或下山高度差的最大值 </p> <p> 然后接下来输入山地图,一共 m行n列,均以空格分隔。 </p> <p> 取值范围: </p> <p> 0 < m ≤ 500 </p> <p> 0 < n ≤ 500 </p> <p> 0 < k < 5 </p>

输出描述

<p> 请问小明能爬到的最高峰多高,到该最高峰的最短步数,输出以空格分隔。 </p> <p> 同高度的山峰输出较短步数。 </p> <p> 如果没有可以爬的山峰,则高度和步数都返回0。 </p> <p> 备注:所有用例输入均为正确格式,且在取值范围内,考生不需要考虑不合法的输入格式。 </p>

示例

示例 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。

时间限制 1000 ms · 内存限制 128 MB

看不懂题目?点开图解
样例1图解:BFS找最高峰及最短步数 0 1 2 0 1 0 0 0 0 1 0 0 1 2 1 3 1 0 0 0 0 0 0 0 9 起点 最高峰 步1 步2 图例 起点 最高峰 路径 k=1 最高高度2 最短步数2
写完代码点「提交」,将对全部测试用例判题。

向老师提问

针对「周末爬山」把疑问、代码和报错填清楚,老师收到后能更快、更准地回复你。