特殊步数的最短旅程

题目描述

快递无人机在棋盘状的仓库内穿行，仓库被划成 $n\times m$ 个格子。无人机需要从起点 $(1,1)$ 飞到终点 $(n,m)$，途中存在无法穿越的障碍格。无人机通常每次只能向右或向下移动一格，但它配备了最多 $k$ 次“跃迁”能力，每次跃迁可以按象棋“马”的走法跳到八个方向之一。请计算到达终点所需的最少步数；若无法到达，输出 $-1$。

输入格式

第一行包含三个整数 $n,m,k$。

接下来 $n$ 行，每行包含 $m$ 个整数，$0$ 表示空地，$1$ 表示障碍。

起点与终点保证为空地。

输出格式

输出一个整数，表示最少步数；若无法到达，输出 $-1$。

输入输出样例 #1

输入 #1

4 4 1
0 0 0 0
0 1 1 0
0 0 0 0
0 1 0 0

输出 #1

5

数据范围

对于 $100\%$ 的数据，$1 \le n,m \le 50$，$0 \le k \le 10$。EOF