题目内容

在一个 $m \times n$ 的网格迷宫中，有一位探险者被困其中，需要找到一条路径，从起点逃到出口。

迷宫中的每个格子可能是以下元素之一：

• $0$：空地，可以自由通行
• $1$：墙壁，无法通行
• $2$：陷阱，可以踏过，但每踩一次会损失 $1$ 点生命值
• $3$：起点（全图仅有一个）
• $4$：出口（全图仅有一个）
• $5$：生命药水，拾取后生命值恢复至满值

探险者初始拥有 $k$ 点生命值。生命值一旦降为 $0$，探险者立即倒下，无法继续移动。探险者每次只能向上、下、左、右四个方向移动到相邻格子，每移动一步，步数加 $1$。

任务：求出探险者从起点到达出口所需的最少步数。若无法到达出口，或在途中因生命值耗尽而倒下，则输出 $-1$。

输入格式

第一行包含三个整数 $m, n, k$，其中 $1 \le m, n \le 50$，$1 \le k \le 20$。

接下来 $m$ 行，每行包含 $n$ 个整数，表示迷宫网格。

输出格式

输出一个整数，表示从起点到出口的最少步数；若无法逃脱，则输出 $-1$。

样例 1

输入

4 5 3
3 0 0 0 0
0 1 0 1 0
0 2 0 2 0
0 0 0 0 4

输出

7

说明

沿上方与右方的墙边行走，共需 $7$ 步。

样例 2

输入

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

输出

-1

说明

出口被墙壁包围，无法到达。

样例 3

输入

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

输出

-1

说明

任何可行路线都必然经过至少一个陷阱，生命值会降为 $0$，机器人损坏，无法到达出口。

样例 4

输入

3 4 2
3 2 0 2
2 0 1 4
5 0 0 2

输出

6

说明

若一开始向右走，会连续经过两个陷阱，生命值降为 $0$；正确路线是一开始向下走，经过一个陷阱后生命值降为 $1$，继续向下拾取生命药水，生命值恢复至 $2$（此时已走 $2$ 步），再向右走 $3$ 步（途中经过一个陷阱，生命值降为 $1$），最后向上走 $1$ 步到达出口，总步数为 $6$。