题目内容

一家物流公司正在开发无人机配送系统。无人机需要从仓库出发，将包裹配送到指定的客户地点。配送区域被划分为一个二维网格，无人机每次可以向上、下、左、右四个方向移动一步。由于电池容量限制，无人机最多只能连续飞行$k$步，之后必须降落在充电站充电（如果没有充电站，则无法继续飞行）。请编写一个程序，计算无人机从起点到终点的最短路径长度。如果无法到达客户地点，返回 $- 1$。

输入描述

配送区域大小：二维矩阵行数$m$，列数$n$，$m$和$n$的取值范围[1,1000]

配送区域表示：矩阵的大小为$m \times n$，数值代表的意义如下：$0$ 表示可飞行的空地。$1$ 表示障碍物（如建筑物、树木等），无人机不能通过。$2$ 表示充电站，无人机可以在此停留并充电。

起点：一个长度为 2 的列表，表示仓库的坐标$\text{start\_row, start\_col}$，左上角坐标为$(0,0)$

终点：一个长度为 2 的列表，表示客户地点的坐标$\text{destination\_row, destination\_col}$

k：无人机最多可以连续飞行的步数。取值范围[1,100000]

输出描述

返回无人机从仓库到客户地点的最短路径长度。如果无法到达客户地点，返回 $- 1$。

样例1

输入

3 3
0 0 0
0 2 0
0 0 0 
0 0
2 2
2

输出

4 

说明

矩阵行数为 3，列数为 3

矩阵第一行为0 0 0

矩阵第二行为0 2 0

矩阵第三行为0 0 0

起点坐标为0 0

终点坐标为2 2

最多连续飞行步数为 2

无人机从(0, 0)出发，路径如下：

$(0, 0) \to (0, 1)$：步数 = 1，剩余可飞行步数 = 1

$(0, 1) \to (1, 1)$：步数 = 2，剩余可飞行步数 = 0

$(1, 1)$是充电站，进入充电站后，剩余可飞行步数重置为 2

$(1, 1) \to (2, 1)$：步数 = 3，剩余可飞行步数 = 1

$(2, 1) \to (2, 2)$：步数 = 4，剩余可飞行步数 = 0

最短路径长度为 4

样例2

输入

3 3
0 0 0
1 1 1
0 0 0
0 0
2 2
2

输出

-1

说明

矩阵行数为 3，列数为 3

矩阵第一行为0 0 0

矩阵第二行为1 1 1

矩阵第三行为0 0 0

起点坐标为0 0

终点坐标为2 2

最多连续飞行步数为 2

无人机从(0, 0)出发，最多只能连续飞行 2 步，但到达(0, 2)后无法继续前进，因为没有充电站，所以无法到达(2, 2)。返回 - 1