[Wikioi 3145] 한 노 타 게임

제목 설명
한 노 타 문 제 는 잘 알려 진 문제 다.A, B, C 세 개의 기둥 에 n 개의 서로 다른 크기 의 원반 (반경 이 각각 1 - n 이 라 고 가정 하 세 요) 이 있 습 니 다. 처음에 그들 은 모두 나의 A 위 에 접 었 습 니 다. (그림 에서 보 듯 이) 당신 의 목 표 는 최소 의 합 법 적 인 이동 단계 에서 모든 접 시 를 A 탑 에서 C 탑 으로 이동 하 는 것 입 니 다.
게임 의 모든 규칙 은 다음 과 같다.
1. 한 걸음 한 접시 만 움 직 일 수 있 습 니 다. (기둥 의 맨 위 에서 다른 기둥 의 맨 위로)
2. 이동 하 는 과정 에서 큰 접시 가 작은 접시 위 에 있 으 면 안 된다 는 것 을 보증 해 야 합 니 다. (작은 것 은 큰 위 에 놓 을 수 있 고 큰 접시 아래 에는 다른 크기 의 접시 가 있어 서 는 안 됩 니 다)
 
n = 3 의 경우 합 법 적 인 이동 시퀀스:
1 from A to C
2 from A to B
1 from C to B
3 from A to C
1 from B to A
2 from B to C
1 from A to C
 
최소 걸음 수의 이동 순 서 를 구하 기 위해 n 을 입력 하 십시오.
입력 설명 입력 설명
정수 n
출력 설명 출력 설명
첫 번 째 줄 의 정수 k 는 가장 적은 이동 걸음 수 를 나타 낸다.
다음 k 줄, 줄 마다 한 마디 씩 N from X to Y 는 N 번 판 을 X 기둥 에서 Y 기둥 으로 이동 하 는 것 을 나타 낸다.X, Y 는 {A, B, C} 에 속한다.
샘플 입력 샘플 입력
3
샘플 출력 샘플 출력
7
1 from A to C
2 from A to B
1 from C to B
3 from A to C
1 from B to A
2 from B to C
1 from A to C
데이터 범위 및 알림 Data Size & Hint
n<=10
 

/*
  ：
      ，         3   ，                 ，                     ：
eg:         top a  n      b  
   ：
1、        top a  n-1      b  ,       a  
2、 a             c  ，c     198-a-b(  'A'+'B'+'C'=198),      top+n-1
3、         top b  n-1      c  ，      
   2、3                ，     1     ，           
*/
#include <stdio.h>
void hanoi(int n,char a,char b,int top) //         top a  n      b  
{
	if(n==1) //       ，     
		printf("%d from %c to %c
",top,a,b);
	else //  ，            
	{
		hanoi(n-1,a,198-a-b,top); //        top a  n-1      c  ,       a  ，c     198-a-b(  'A'+'B'+'C'=198)
		hanoi(1,a,b,top+n-1); // a             b  ,      top+n-1
		hanoi(n-1,198-a-b,b,top); //         top c  n-1      b  ，      
	}
}
int main()
{
	int n,i,m=0;
	scanf("%d",&n);
	for(i=1;i<=n;i++) //    n          
		m=2*m+1;
	printf("%d
",m);
	hanoi(n,'A','C',1);
	return 0;
}