题目描述

蜂巢是由蜜蜂建造的大量蜡质巢房，可以描述为欧几里得平面的正则镶嵌，其中每个内部顶点处有三个六边形相交。六边形的内角为 120 度，因此三个六边形在一点处构成完整的 360 度。下图展示了一个拥有 3 行 4 列的完整蜂巢。

:::align{center} :::

在此我们保证第二列的第一个蜂房始终位于第一列第一个蜂房的右下侧，如上图所示。一个一般的蜂巢可能在一个完整蜂巢的基础上去掉相邻蜂房之间的一些墙壁，但整个蜂巢仍然是闭合的。一个可能的情形如下图所示。

:::align{center} :::

Hamilton 是一只生活在普通蜂巢里的勇敢蜜蜂。现在，他想从一个起点移动到一个指定的目的地。下图展示了一个在 $3 \times 4$ 蜂巢中，从第 2 列第 1 个蜂房到第 4 列第 1 个蜂房的可行路径。

:::align{center} :::

请帮助他找到从指定起点到目的地的可行路径所需经过的最少蜂房数（包括起点和终点）。

输入格式

输入包含多组测试数据，第一行包含一个正整数 $T$，表示测试数据组数，最多为 $10^4$。

对于每组测试数据，第一行包含两个整数 $r$ 和 $c$，分别表示蜂巢的行数和列数，满足 $2 \leq r, c \leq 10^3$。

接下来的 $(4 r + 3)$ 行描述整个给定的蜂巢，每行包含最多 $(6 c + 3)$ 个字符。奇数行包含以加号（“$+$”）表示的网格顶点以及零个或多个水平边，而偶数行包含两个或多个斜边。具体来说，一个蜂房由 $6$ 个顶点和最多 $6$ 条边描述。它的上边界或下边界由三个连续的减号（“$-$”）表示。每条斜边（如果存在）是一个正斜杠（“/”）或反斜杠（“\”）字符。所有边字符都将正好放置在相应的顶点之间。在起始蜂房（对应地，目的蜂房）的中心，使用大写字母 “S”（对应地，大写字母 “T”）作为特殊字符来标记该特殊蜂房。所有其他字符均为空格字符。注意，如果任何输入行可能包含末尾空格，这些空格将被省略。

我们保证所有最外层的墙都存在，因此给定的蜂巢是闭合的，并且 “S” 和 “T” 在给定的蜂巢中各出现恰好一次。此外，所有测试数据的 $r \cdot c$ 之和不超过 $2 \times 10^6$。

输出格式

对于每组测试数据，输出一行包含 Hamilton 从起始蜂房（“S”）移动到目的地（“T”）所需经过的最少蜂房数，包括起始和目的蜂房。如果不存在可行路径，则输出 -1。

1
3 4
  +---+       +---+
 /     \     /     \
+       +---+       +---+
 \           \     /     \
  +   +   S   +---+   T   +
 /     \     /           /
+       +---+       +   +
 \           \     /     \
  +---+       +---+       +
 /                       /
+       +---+       +   +
 \                 /     \
  +---+       +---+       +
       \     /     \     /
        +---+       +---+

7

提示

翻译由 DeepSeek V4 Pro 完成