SP5465 DP - Deliver pizza

在一个 $n\times m$ 的矩阵里，只有一个格子是字符 `X`，表示 pizza 店所在地。 pizza 店有两个学徒，他们负责每天送 pizza。在矩阵里： 1. 字符 `$` 表示该格子是一座写字楼 **（注意，在本题中，pizza 店本身也是写字楼）**，里面的客户订了一个 pizza。 2. 字符 `0`~`9`表示该格子是空地，同时表示该空地的高度。每个空地格子的高度范围为 $[0,9]$。 学徒每次只能给**一个客户**送 pizza，然后**返回 pizza 店**再去给下一个客户送 pizza。学徒可以从当前格子往上、下、左、右四个方向移动一格。当然根据高度的不同，移动一次的时间也不同。 你能从 $A$ 格子进入 $B$ 格子的条件是： 1. $A,B$ 两个格子相邻 **（有一条公共边）**； 2. 关于移动方法（因为原题讲的不清楚，译者~~以身试法~~试了几回，才确定的）： - 如果 $A,B$ 均为**空地**： - 如果 $A,B$ 高度相等，那么花费的时间是 $1$； - 如果 $A,B$ 高度差为 $1$，那么花费的时间是3； - 如果高度差大于 $1$，则不能从 $A$ 走到 $B$。 - 如果 $A$ 与 $B$ 当中，**至少有一个格子是写字楼（包括两个格子都是写字楼的情况）**： - 花费的时间是 $2$（如果 $A$ 或 $B$ 当中有空地的话，**不需要考虑 $A$ 或 $B$ 的高度**）。 注意：学徒可以进入写字楼，即使他不是给该写字楼的客户送 pizza（也就是可以借道）。 一开始的时刻是 $0$，给你对应的 $n\times m$ 矩阵，问最早在哪个时刻，这两个学徒能把所有 pizza 送完？送完所有 pizza 后，学徒们不需要回到 pizza 店。如果无法完成工作，输出 $-1$。

本题由多组数据构成。 第一行一个整数 $T$，表示数据组数。 对于每组数据： 第一行有两个整数 $n,m$，表示矩阵的行数和列数。 接下来是一个 $n\times m$ 的字符矩阵，每个字符要么是数字，要么是 `X` 或 `$`，意义同上文所述。字符之间没有空格分隔。

输出 $T$ 行。 对于每组数据，输出一个整数，表示送完 pizza 的最早时刻。如果不可能送完 pizza，就输出 $-1$。

$2\le n,m \le 50$。 最多只会有 $20$ 座写字楼。 感谢 @info___tion 提供的翻译。