小慕正在规划一次户外徒步活动。地图用一个 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