HDU 1997汉诺塔VII

又是汉诺塔~

回顾一下汉诺塔的移动过程。

从左到右设为A,B,C 3个盘子的时候

1: No.1 A -> C

2: No.2 A -> B

3: No.1 C -> B

4: No.3 A -> C

5: No.1 B -> A

6: No.2 B -> C

7: No.1 A -> C

.把第n个盘子移动到C前，第n-1个盘子要移动到B。也就是说，此时，如果第n-1个盘子在 C就是错误的，而第n个盘子在B就是错误的。那么就可以进行递归判断。调用check(intn,int A,int B,int C) A为移动的起点，C为终点。此时的盘子只能在A或者C上。

若n在A上，那么第n-1个要么在B上要么在A上，绝不可能在C上。换句话说，此时起点应该为A,而终点为B。所以调用改为：check(n-1,A,C,B);

若n在C上，那么第n-1 要么在B上，要么在C上，绝不可能在A上，换句话说，此时起点应该为B,而终点为C。 check(n-1,B,A,C);

#include <cstdio>

#include <cstring>

const int MAXN=64+10;

int a[4][MAXN],cur[4];

bool flag;

void check(int n,int A,int B,int C)

{

	if(n==0) { flag=true; return ;}

	if(a[A][cur[A]]==n)

	{

			cur[A]++;

			check(n-1,A,C,B);

	}

	else if(a[C][cur[C]]==n)

	{

			cur[C]++;

			check(n-1,B,A,C);

	}

	else { flag=false; return ;}

}

int main()

{

    int T;

    scanf("%d",&T);

    while (T--)

    {

		memset(a,0,sizeof(a));

		int n;

		scanf("%d",&n);

		for(int i=1;i<=3;i++)

		{

				scanf("%d",&a[i][0]);

				for(int j=1;j<=a[i][0];j++)

					scanf("%d",&a[i][j]);

		}

		cur[1]=cur[2]=cur[3]=1;

		flag=false;

		check(n,1,2,3);

		if(flag)

			printf("true\n");

		else

			printf("false\n");

	}

    return 0;

}

巴特西

HDU 1997汉诺塔VII

最新文章

热门文章