题面描述

小塔准备在周末去爬山锻炼，山地图以二维矩阵表示，其中0代表平地，1到9表示不同的山高度。小塔每次只能向上下左右四个方向移动一格，且移动到相邻位置的高度差不能超过k。小塔从左上角的$(0,0)$位置出发，要求找到能够到达的最高峰的高度以及到达该峰的最短步数。如果无法到达任何山峰，则输出0 0。

思路

这道题可以通过广度优先搜索（BFS）来解决。具体步骤如下：

1. 初始化：
   • 使用一个m x n的数组visited来记录每个位置是否已经被访问过，以及到达该位置的步数。

题目内容

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