2014-01-30 15:07:37Morris
[ZJ][遞迴] d734. 另类Hanoi
內容 ：
设有n个大小不同的中空圆盘，按从小到大的顺序从1到n编号。将这n个圆盘任意的迭套在三根立柱上，立柱的编号依次为 a、b、c ，这个状态称为初始状态。
现在要求找到一种步数最少的移动方案，使得从初始状态转变为目标状态。
移动时有如下要求：
* 一次只能移动一个盘。
* 不允许把大盘移到小盘上面。
輸入說明 ：
第一行数字n(1<=n<=20)，表示状态中圆盘总数。
第二行表示初始状态，有n个数字，第i个数字a[i]表示第i个圆盘放在第a[i]个立柱上。
第三行表示目标状态，有n个数字，第i个数字b[i]表示第i个圆盘放在第b[i]个立柱上。
不必EOF判断。
輸出說明 ：
输出移动步骤时，需按照 ring x : y -> z 的格式，其中x为整数，y、z为a、b、c其中一个。
最后在输出最少步数。
最后在输出最少步数。
範例輸入 ：
5 1 1 1 2 2 3 1 2 2 2
範例輸出 ：
ring 1 : a -> b ring 2 : a -> c ring 1 : b -> c ring 3 : a -> b ring 1 : c -> b ring 2 : c -> a ring 1 : b -> c 7
將問題拆成 "隨便一個狀態集中到某一個目標柱上" 和 "某一個狀態到另一個狀態"
#include <stdio.h>
#define mod 1000000007
int init[25], goal[25], n;
int ret = 0;
char label[] = " abc";
void hanoiArbitrarily(int n, int goal) {
if(n == 0)
return;
if(init[n] != goal) {
int target = 6;//temp buffer.
target -= init[n];
target -= goal;
hanoiArbitrarily(n-1, target);// move others into buffer.
printf("ring %d : %c -> %c\n", n, label[init[n]], label[goal]);
init[n] = goal;//move n-th disk to goal.
ret++;
hanoiArbitrarily(n-1, goal);
} else {
hanoiArbitrarily(n-1, goal);
}
}
void hanoi(int n) {
if(n == 0) return;
if(init[n] != goal[n]) {
int target = 6;
target -= init[n];
target -= goal[n];
hanoiArbitrarily(n-1, target);
for(int i = 1; i < n; i++)
init[i] = target;
printf("ring %d : %c -> %c\n", n, label[init[n]], label[goal[n]]);
ret++;
init[n] = goal[n];//move n-th disk to goal.
}
hanoi(n-1);
}
int main() {
int i;
while(scanf("%d", &n) == 1 && n) {
for(i = 1; i <= n; i++)
scanf("%d", &init[i]);
for(i = 1; i <= n; i++)
scanf("%d", &goal[i]);
ret = 0;
hanoi(n);
printf("%d\n", ret%mod);
}
return 0;
}