AT_indeednow_2015_finala_b Office Ninja

Indeed 社的办公室是由正六边形拼接而成的。 新入职的 A 君擅长运动，因此可以跳过正六边形之间的隔板进行移动。 现在，A 君需要从地点 $s$ 急速移动到地点 $t$。 但是，在从 $s$ 移动到 $t$ 的过程中，每当进入一个正六边形空间时，里面的人都会问他“How are you?”，这会花费一些时间。 而且，如果某个正六边形空间里有 $n$ 个人，A 君就会被问 $n$ 次“How are you?”。 请问，A 君从 $s$ 移动到 $t$ 的过程中，最少会被问多少次“How are you?”？ 注意，在 $s$ 和 $t$ 两个地点不会被问“How are you?”。

输入如下格式： > $R$ $C$ $a_{11}$ $a_{12}$ ... $a_{1C}$ $a_{21}$ $a_{22}$ ... $a_{2C}$ ... $a_{R1}$ $a_{R2}$ ... $a_{RC}$ - 第 1 行包含办公室由正六边形拼成的行数 $R$ 和列数 $C$（$1 \leq R, C \leq 100$，$R \times C \geq 2$）。 - 接下来的 $R$ 行，每行 $C$ 个字符，表示每个正六边形空间里的人数 $a_{ij}$。 - $a_{ij}$ 的取值为 `s`、`t` 或 `0` 到 `9` 之间的数字字符。 - 所有 $a_{ij}$ 中，恰好有一个为 `s`，恰好有一个为 `t`。 - $a_{ij}$ 与实际输入的对应关系请参考下图。 

请输出一个整数，表示最少会被问多少次“How are you?”。

### 样例解释 1  由 ChatGPT 4.1 翻译