题目内容

在山区突发的林火救援任务中，无人机需要将急救物资从山脚的物资营地运送到山顶的临时指挥所。任务区域被简化为一个 $M \times N$ 的网格，行从上到下、列从左到右分别表示由山脚向山顶的方向。无人机只能向下 $D$ 或向右 $R$ 飞行，从左上角的营地 $(0,0)$ 飞到右下角指挥所 $(M-1, N-1)$。

每个位置的状态用一个整数表示：

• 值 $0$：正常空地；
• 值 $d (1 \le d \le 49)$：火源（山林中的明火点），其热扰强度为 $d$；
• 值 $-1$：坍塌区（山体滑坡或浓烟封锁），无人机不可进入。

当无人机经过位置 $(x, y)$ 时，各火源点的热扰场会影响其飞行信号损耗。设火源位于 $(x_f, y_f)$，强度为 $d$，无人机当前格子与该火源的曼哈顿距离为

则该火源对当前格子的信号损耗贡献为：

1. 若 $dist = 0$ 即经过火源本身：信号损耗增加 $d$；
2. 若 $0 < dist < d$：信号损耗增加 $(d - dist)$；
3. 若 $dist \ge d$：该火源对当前格子无影响。

一个位置的最终信号损耗，是所有火源贡献之和；坍塌区虽不参与损耗叠加，但任何路径都不能进入坍塌区格点。

此外，任务还受以下约束：

• 航向变更限制：无人机飞行方向发生一次变化（由 D 变为 R，或由 R 变为 D）称为一次"航向变更"。整条路径允许的航向变更次数不超过给定的 $K$。注意：相邻两步若方向相同则不算变更；起点不需要单独计入一次航向。
• 可行性：若起点 $(0,0)$ 本身是坍塌区（即输入中 $\text{grid}[0][0] = -1$），或终点 $(M-1,N-1)$ 是坍塌区，则不存在合法路径。

请计算满足以上约束、能够从营地到达指挥所的飞行路径中，总信号损耗的最小值，并输出该最小值。若不存在任何合法路径（被障碍完全切断，或任何可达路径上的航向变更次数都超过 $K$），输出 $-1$。

输入描述

第一行包含三个整数 $M, N, K$，分别表示网格行数、列数与允许的最大航向变更次数。其中 $0 \le K \le 200$。

接下来 $M$ 行，每行包含 $N$ 个整数，表示每个位置的网格值。每个值的范围为 $\{-1, 0, 1, 2, \dots, 49\}$，其中 $-1$ 表示坍塌区，$0$ 表示空地，$d \ge 1$ 表示强度为 $d$ 的火源。

输出描述

输出一个整数，表示从 $(0,0)$ 到达 $(M-1,N-1)$ 在所有合法路径中的最小信号损耗。若不存在任何合法路径，输出 $-1$。

数据范围

• $1 \le M, N \le 200$
• $0 \le K \le 200$
• 网格元素取值范围为 $\{-1, 0, 1, 2, \dots, 49\}$
• 时间复杂度按 $O(M \cdot N \cdot K)$ 估计，最坏为 $8 \times 10^6$，可在常规时间限制内通过；总损耗远小于 $2^{31}$，可用 32 位有符号整数存储。

分档：

• 对于 $40\%$ 的数据：$M \le 8$ 且 $N \le 8$，$K \le 4$
• 对于 $70\%$ 的数据：$M \le 60$ 且 $N \le 60$，$K \le 60$
• 对于 $100\%$ 的数据：$M \le 200$ 且 $N \le 200$，$K \le 200$

样例1

输入

1 1 0
3

输出

3

说明

$M=N=1$，起点与终点重合，无人机无需飞行，航向变更次数为 $0$。由于起点 $(0,0)$ 自身就是一个强度为 $3$ 的火源，根据规则 1，总信号损耗为 $3$。此用例演示了 $M=N=1$ 时起点恰好为火源的边界情况。

样例2

输入

3 3 5
0 0 0
0 3 0
0 0 0

输出

7

说明

中心 $(1,1)$ 是一个强度为 $3$ 的火源，因此各格的累积信号损耗为：

$K=5$ 对任何单调路径都足够大（$3\times 3$ 网格从 $(0,0)$ 到 $(2,2)$ 共 $4$ 步，航向变更最多 $3$ 次）。6 条单调路径中：

• DDRR、RRDD（均绕过中心格）：$1+2+1+2+1=7$；
• DRDR、DRRD、RDDR、RDRD（均经过中心格的损耗 $3$）：总损耗均为 $9$。

因此最小总损耗为 $7$。此用例演示了"热扰场"叠加后的路径选择：是否经过火源本身会让损耗差异显著。

样例3

输入

4 4 2
0 -1 0 0
0  0 0 0
0  0 0 0
-1 0 0 0

输出

0

说明

网格中没有火源（所有非 $-1$ 的格子值均为 $0$），因此只要避开坍塌区 $(0,1)$ 和 $(3,0)$，每条合法路径的总损耗都是 $0$。

当 $K=2$ 时可行的两条路径分别是：

• DRRRDD：$(0,0)\to(1,0)\to(1,1)\to(1,2)\to(1,3)\to(2,3)\to(3,3)$，航向变更序列为 D→R→D，共 $2$ 次；
• DDRRRD：$(0,0)\to(1,0)\to(2,0)\to(2,1)\to(2,2)\to(2,3)\to(3,3)$，航向变更序列为 D→R→D，共 $2$ 次。

此用例演示了障碍迫使路径额外增加一次航向变更的情形：单纯直走的两条$K=1$路径都被障碍截断。

样例4

输入

4 4 1
0 -1 0 0
0  0 0 0
0  0 0 0
-1 0 0 0

输出

-1

说明

与样例3相同的网格，但 $K$ 收紧到 $1$。此时所有可行的单调路径需要至少 $2$ 次航向变更（见样例3说明），而 $K=1$ 不允许任何路径走完所需的两次 D→R→D 切换，因此不存在合法路径，输出 $-1$。

此用例对照样例3，演示同一网格在 $K$ 减 $1$ 时从有解变为无解。