汉诺塔谜题 - 문제

小青鱼的桌子上有三根柱子，分别标记为 A、B 和 C。他还有 $n$ 个大小互不相同的圆盘，从小到大依次编号为 $1$ 到 $n$。初始时，所有圆盘都叠放在柱子 A 上，且较小的圆盘在较大的圆盘上方。

小青鱼想要将这个初始状态转换为给定的目标状态。与经典的汉诺塔不同，这个谜题允许以下一种特殊的移动方式。

在一次移动中，小青鱼执行以下操作：

等价地，一次移动会从源柱子上取下最上方的圆盘，并将其插入到另一根不同的目标柱子中，位于该目标柱子上所有较小圆盘的下方、所有较大圆盘的上方。目标柱子上原本圆盘的相对顺序不会改变。

一个状态可以用一个字符串来表示。对于一个状态字符串 $t$，$t$ 的第 $i$ 个字符表示包含圆盘 $i$ 的柱子，其中圆盘 $i$ 是第 $i$ 小的圆盘。由于每根柱子上的圆盘总是满足较小的圆盘在较大的圆盘上方，因此这样的字符串唯一确定了整个状态。

例如，下图展示了第一个样例中的一次移动。

样例 1 中的一次移动：CAAAAA → CCAAAA

目标状态由字符串 $s$ 指定。$s$ 的第 $i$ 个字符是圆盘 $i$ 在最终状态中必须所在的柱子。

帮助小青鱼计算从初始状态到达目标状态所需的最小移动次数。

输入包含多组测试数据。第一行包含一个整数 $T$ ($1 \le T$)，表示测试数据的组数。

对于每组测试数据，第一行包含一个非空字符串 $s$，仅由字符 A、B 和 C 组成。$s$ 的长度为对应测试数据中的圆盘数量，且 $s$ 的第 $i$ 个字符指定了圆盘 $i$ 在最终状态中必须所在的柱子。

保证所有测试数据的 $|s|$ 之和不超过 $3 \times 10^6$。

对于每组测试数据，输出一行，包含一个整数，表示从初始状态到达目标状态所需的最小移动次数。

4
BCABCA
BCBAB
AAAAAAAAABC
BACBACBACBACBACBACBACBACBAC

对于第一组测试数据，一种最优策略为：

$$AAAAAA \to CAAAAA \to CCAAAA \to CCBAAA \to CCBBAA \to CCBBCA \to CCABCA \to BCABCA$$

对于第二组测试数据，一种最优策略为：

$$AAAAA \to BAAAA \to BCAAA \to BCBAA \to BCBCA \to BCBCB \to BABCB \to BABAB \to BCBAB$$

QOJ.ac