#P18389. Hanoi Tower Puzzle
Hanoi Tower Puzzle
Hanoi Tower Puzzle
有三根柱子 A、B、C,以及大小互不相同的 个圆盘。圆盘从小到大编号为 。初始全部圆盘都在 A 柱,较小的盘在较大的盘上方。
每次移动按以下规则进行:
- 从一根非空柱子取下最顶端的圆盘。
- 选择另一根柱子作为目标柱。
- 暂时提起目标柱上所有比当前圆盘更小的盘,保持这些盘的相对次序。
- 放入当前圆盘,再把提起的盘按原次序放回。
以上全过程算作一次移动。换言之,你只能从源柱取顶盘,但在目标柱可以把这个盘直接插入所有较小盘之下、所有较大盘之上。目标柱原有盘的相对次序不变。它不同于经典汉诺塔,不要求目标柱顶盘比被移动的盘大。
用字符串表示状态:第 个字符是第 小的盘所在的柱子。每根柱上的大小顺序始终固定,所以这个字符串唯一确定整个状态。
例如,CAAAAA 可以一步变成 CCAAAA:从 A 柱取下顶端的2号盘,暂时提起 C 柱的1号盘,把2号盘插到其下方,再放回1号盘。临时提起和放回不另计移动次数。

给出目标状态字符串 ,求从所有盘都在 A 柱的初始状态到达 的最少移动次数。
输入格式
第一行一个整数 ,表示测试用例数。
每组一行非空字符串 ,仅含大写字符 A、B、C。其长度就是圆盘数,左起第 个字符规定第 小圆盘的目标柱。
全部测试用例的字符串长度之和不超过 。
输出格式
每组输出一行一个整数,表示最少移动次数。答案可能超过有符号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