汉诺塔VII |
| Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) |
| Total Submission(s): 863 Accepted Submission(s): 642 |
|
Problem Description
n个盘子的汉诺塔问题的最少移动次数是2^n-1,即在移动过程中会产生2^n个系列。由于发生错移产生的系列就增加了，这种错误是放错了柱子，并不会把大盘放到小盘上，即各柱子从下往上的大小仍保持如下关系 ： n=m+p+q a1>a2>...>am b1>b2>...>bp c1>c2>...>cq ai是A柱上的盘的盘号系列，bi是B柱上的盘的盘号系列， ci是C柱上的盘的盘号系列，最初目标是将A柱上的n个盘子移到C盘. 给出1个系列，判断它是否是在正确的移动中产生的系列. 例1：n=3 3 2 1 是正确的 例2：n=3 3 1 2 是不正确的。 注：对于例2如果目标是将A柱上的n个盘子移到B盘. 则是正确的.
|
|
Input
包含多组数据，首先输入T,表示有T组数据.每组数据4行，第1行N是盘子的数目N<=64. 后3行如下 m a1 a2 ...am p b1 b2 ...bp q c1 c2 ...cq N=m+p+q,0<=m<=N,0<=p<=N,0<=q<=N,
|
|
Output
对于每组数据，判断它是否是在正确的移动中产生的系列.正确输出true，否则false
|
|
Sample Input
6 3 1 3 1 2 1 1 3 1 3 1 1 1 2 6 3 6 5 4 1 1 2 3 2 6 3 6 5 4 2 3 2 1 1 3 1 3 1 2 1 1 20 2 20 17 2 19 18 16 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 |
|
Sample Output
true false false false true true |
|
Author
Zhousc@ECJTU
|
|
Source
ECJTU 2008 Spring Contest
|
|
Recommend
lcy
|
解题思路：
对一个含有n个盘子，从A柱移动到C柱借助B柱的汉诺塔，第n个盘子移动到C柱过程是这样子的：首先将其余的n-1个盘子移动到B柱，然后第n个盘子直接移动到C柱。在这过程中，第n个盘子只出现在A柱和C柱两个柱子上，也即第n个盘子不可能出现在B柱上。因此对于当前移动的盘子，只需检查其所在的柱子是否符合这个要求，如果出现在B柱上，则显然进入了错误移动中。这是本题求解思想精髓所在。汉诺塔是个递归求解过程，假设第n个盘子符合要求，则判别的下一个目标是第n-1个盘子。若第n个盘子在A柱上，此时剩余n-1个盘子必由A柱移动到B柱，经由C柱。此时对第n-1个盘子，C柱就是其不可能出现的位置；若第n个盘子在C住上，这剩余n-1个盘子则是在B柱上，经由A柱，移动到C柱上，因此，A柱就是第n-1个盘子不可能出现的位置。
根据汉诺塔递归求解的过程，对每个移动的盘子，可以用递归求解的方式判断。代码如下：
#include<iostream> #include<cstdio> #include<cstring> using namespace std; int flag; void DFS(int n,int *A,int *B,int *C){ if(n==0){ flag=true; return; } if(B[0] && n==B[1]){ flag=false; return ; } if(A[0] && n==A[1]){ A[1]=A[0]-1; DFS(n-1,++A,C,B); }else if(C[0] && n==C[1]){ C[1]=C[0]-1; DFS(n-1,B,A,++C); } } int main(){ //freopen("input.txt","r",stdin); int A[70],B[70],C[70]; int t,n; scanf("%d",&t); while(t--){ scanf("%d",&n); scanf("%d",&A[0]); for(int i=1;i<=A[0];i++) scanf("%d",&A[i]); scanf("%d",&B[0]); for(int i=1;i<=B[0];i++) scanf("%d",&B[i]); scanf("%d",&C[0]); for(int i=1;i<=C[0];i++) scanf("%d",&C[i]); DFS(n,A,B,C); if(flag) puts("true"); else puts("false"); } return 0; }
题目分析：
1） 最初我们要判断一下是不是已经完全放好了，这样就不用考虑是不是最优化了， 因为都已经放好了，肯定是最合法的！ 或者说全部在 A 上，这是还没开始动作的一个状态，所以也是合法的！
2） 否则我们 要对每次状态的最大的那个进行判断，因为我们知道，汉诺塔最大的那个不可能停在 B 上，（假设 最初的时候都在 A 上，要移到 C 上去！），只可能在 A 或者 C 上面！如果是放在 B 上面，停止判断，直接断定他非法～这样我们得出了第二个判段依据！
3） 如果最大的在 A 上面，我可以想到的是，他还没有放在 C 上，此时这个状态的上面一系列状态都是想把其他的放在 B 上，然后就可以把 A 放到 C 上了，所以我们在这里做出更新，因为他上面一系列动作都是想让 A 上面的除最大的外都放到 B 上面去，所以，我们这个时候往上考虑，对 N-1 进行 判断！这个时候动作的方向是 A->B 所以为了统一操作，我们得把 B 跟C互换！
4） 如果最大的在 C 上面，这时候倒数第二大的不是放在 B 上就是 C 上，我们要把要把倒数第二大的以及其他的放在 C 上，这时候的动作方向是 B—>C ;所以把 A 跟 B 交换一下！
#include<stdio.h> int a,b,c,flag; int one[4],num[4],h[4][70]; int main(){ //freopen("input.txt","r",stdin); int t,n; scanf("%d",&t); while(t--){ a=1,b=2,c=3; one[a]=one[b]=one[c]=1; scanf("%d",&n); scanf("%d",&num[a]); for(int i=one[a];i<=num[a];i++) scanf("%d",&h[a][i]); scanf("%d",&num[b]); for(int i=one[b];i<=num[b];i++) scanf("%d",&h[b][i]); scanf("%d",&num[c]); for(int i=one[c];i<=num[c];i++) scanf("%d",&h[c][i]); flag=1; int tmp; while(1){ if(num[c]==n || num[a]==n) break; if(num[b]>0 && h[b][one[b]]==n){ flag=0; break; } if(num[a]>0 && h[a][one[a]]==n){ n--; num[a]--; one[a]++; tmp=b;b=c;c=tmp; continue; } if(num[c]>0 && h[c][one[c]]==n){ n--; num[c]--; one[c]++; tmp=a;a=b;b=tmp; continue; } } if(flag) printf("true\n"); else printf("false\n"); } return 0; }