Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 203 Accepted Submission(s): 174
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
是不正确的。
注:對于例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
Sample Output
#include <iostream>
#include <stdio.h>
using namespace std;
int main()
{
int one[4],n[4],h[4][64],a,b,c,N,cas,i,t,flag;
scanf("%d",&cas);
while(cas--)
{
a = 1;b = 2;c = 3;
one[a]=one[b]=one[c]=1;
scanf("%d",&N);
scanf("%d",&n[a]);
for(i = one[a];i<=n[a];i++)
scanf("%d",&h[a][i]);
scanf("%d",&n[b]);
for(i = one[b];i<=n[b];i++)
scanf("%d",&h[b][i]);
scanf("%d",&n[c]);
for(i = one[c];i<=n[c];i++)
scanf("%d",&h[c][i]);
flag = 1;
while(true)
{
if(n[b]>0&&h[b][one[b]]==N){flag = 0;break;}
if(n[c]==N||n[a]==N){flag = 1;break;}
if(n[a]>0&&h[a][one[a]]==N)
{
N--;
n[a]--;
one[a]++;
t = b; b = c;c = t;
continue;
}
if(n[c]>0&&h[c][one[c]]==N)
n[c]--;
one[c]++;
t = a;a = b;b = t;
}
if(flag)printf("true\n");
else printf("false\n");
}
return 0;
}
本文轉自NewPanderKing51CTO部落格,原文連結:http://www.cnblogs.com/newpanderking/archive/2011/07/29/2120984.html ,如需轉載請自行聯系原作者