SP3647 MOEBIUS - Moebius

尽管「莫比乌斯」游戏鲜为人知，但仍有一些狂热者每天都在沉迷这款游戏。在游戏中，玩家的目标是找出一种方法，以最低代价清除莫比乌斯带上的一对方格，其中一格包含 $x$，另一格包含 $z$。 莫比乌斯带由一个 $M \times N$ 的矩形纸张构成，标记为 $ABCD$。这张纸的两面都包含一个由 $1 \times 1$ 方格组成的网格。在这两个面上，列编号从 $1$ 到 $N$，行编号从 $1$ 到 $M$，起点都是 $A$ 角。此外，位于第 $i$ 行和第 $j$ 列的方格 $(i, j)$ 可以容纳 $x$、$z$ 或为空（用 "." 表示）。将纸张扭转半圈后，将 $A$ 端与 $C$ 端、$B$ 端与 $D$ 端相连，形成一个只剩下一个表面的莫比乌斯带，这就是游戏中的平台。 图示为两次连续清除操作，其代价分别为 $5$ 和 $8$。只有当两个方格之间有一条路径可以通过连续的四个空方格相连，并且这条路径的转折不超过两次时，才可以清除 $x$ 和 $z$。路径上的空方格可以超出莫比乌斯带的范围。清除一对方格的成本是两格之间最短路径的长度。清除后，原位置变为空方格。 你的任务是编写一个程序，通过最多进行一次额外的中间清除，以最低的总体代价清除给出的一对包含 $x$ 和 $z$ 的方格。

输入包含多个数据集。第一行是一个正整数，表示数据集的数量，最大不超过 $20$。 每个数据集的第一行有两个用空格分隔的整数 $M$ 和 $N$（$1 \le M, N \le 1000$）。接下来两行，每行以 'C u v' 格式描述要清除的方格，其中 $C$ 为 'F' 表示前面，'B' 表示后面，$u$ 和 $v$ 是方格在原始矩形中的行列坐标。 接下来的 $M$ 行描述了莫比乌斯带的前面，每行含有 $N$ 个字符，表示每一行的内容（'x', 'z', 或 '.' 空方格）。 然后，再有 $M$ 行描述莫比乌斯带的背面，同样是 $N$ 个字符，表示每一行的内容。

对于每个数据集，输出一行，表示最小的总代价。如果无法通过最多一次中间清除清除给定的方格对，则输出 `-1`。 **本翻译由 AI 自动生成**