#P18389. Hanoi Tower Puzzle

Hanoi Tower Puzzle

Hanoi Tower Puzzle

有三根柱子 A、B、C,以及大小互不相同的 nn 个圆盘。圆盘从小到大编号为 1,2,…,n1,2,\ldots,n。初始全部圆盘都在 A 柱,较小的盘在较大的盘上方。

每次移动按以下规则进行:

  1. 从一根非空柱子取下最顶端的圆盘。
  2. 选择另一根柱子作为目标柱。
  3. 暂时提起目标柱上所有比当前圆盘更小的盘,保持这些盘的相对次序。
  4. 放入当前圆盘,再把提起的盘按原次序放回。

以上全过程算作一次移动。换言之,你只能从源柱取顶盘,但在目标柱可以把这个盘直接插入所有较小盘之下、所有较大盘之上。目标柱原有盘的相对次序不变。它不同于经典汉诺塔,不要求目标柱顶盘比被移动的盘大。

用字符串表示状态:第 ii 个字符是第 ii 小的盘所在的柱子。每根柱上的大小顺序始终固定,所以这个字符串唯一确定整个状态。

例如,CAAAAA 可以一步变成 CCAAAA:从 A 柱取下顶端的2号盘,暂时提起 C 柱的1号盘,把2号盘插到其下方,再放回1号盘。临时提起和放回不另计移动次数。

一次移动示意:将2号盘插到1号盘下方

给出目标状态字符串 ss,求从所有盘都在 A 柱的初始状态到达 ss 的最少移动次数。

输入格式

第一行一个整数 T≥1T\ge1,表示测试用例数。

每组一行非空字符串 ss,仅含大写字符 A、B、C。其长度就是圆盘数,左起第 ii 个字符规定第 ii 小圆盘的目标柱。

全部测试用例的字符串长度之和不超过 3⋅1063\cdot10^6。

输出格式

每组输出一行一个整数,表示最少移动次数。答案可能超过有符号32位整数范围。

样例输入 1

4
BCABCA
BCBAB
AAAAAAAAABC
BACBACBACBACBACBACBACBACBAC

样例输出 1

7
8
20
88

样例说明

第一组的一条最优状态序列为:

AAAAAA -> CAAAAA -> CCAAAA -> CCBAAA -> CCBBAA -> CCBBCA -> CCABCA -> BCABCA

第二组的一条最优状态序列为:

AAAAA -> BAAAA -> BCAAA -> BCBAA -> BCBCA -> BCBCB -> BABCB -> BABAB -> BCBAB