CF677D Vanya and Treasure

Vanya 正位于一座可以表示为 $n \times m$ 网格的宫殿中。每个房间都装有一个宝箱，位于第 $i$ 行第 $j$ 列的房间内放有类型为 $a_{ij}$ 的宝箱。对于每种 $x \leq p - 1$ 的宝箱，其内都藏有可以开启任意一只类型为 $x+1$ 宝箱的钥匙，而所有类型为 $1$ 的宝箱都没有上锁。恰好存在一只类型为 $p$ 的宝箱，其中藏有宝藏。 Vanya 从左上角单元格 $(1,1)$ 出发。请问，Vanya 至少需要行走多少总距离，才能拿到包含宝藏的类型为 $p$ 的宝箱？我们认为，从单元格 $(r_1,c_1)$ 到 $(r_2,c_2)$ 的距离为 $|r_1 - r_2| + |c_1 - c_2|$。

输入的第一行包含三个整数 $n$、$m$ 和 $p$（$1 \leq n,m \leq 300, 1 \leq p \leq n \cdot m$），分别表示宫殿的行数、列数和宝箱种类数。 接下来的 $n$ 行，每行包含 $m$ 个整数 $a_{ij}$（$1 \leq a_{ij} \leq p$），表示对应房间宝箱的类型。保证每种 $x$ 从 $1$ 到 $p$ 都至少有一个宝箱（也就是说，必然存在一组 $(r,c)$ 使得 $a_{rc} = x$）。另外，保证恰好只有一个类型为 $p$ 的宝箱。

输出一个整数，表示 Vanya 至少需要行走的距离和，才能拿到藏有宝藏的类型为 $p$ 的宝箱。

由 ChatGPT 5 翻译