wiki 3145 한 노 타의 출력 과정

제목 설명 Description
한 노 타 문 제 는 잘 알려 진 문제 다.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 을 입력 하 십시오.
입력 설명 Input Description
정수 n
출력 설명 Output Description
첫 번 째 줄 의 정수 k 는 가장 적은 이동 걸음 수 를 나타 낸다.
다음 k 줄, 줄 마다 한 마디 씩 N from X to Y 는 N 번 판 을 X 기둥 에서 Y 기둥 으로 이동 하 는 것 을 나타 낸다.X, Y 는 {A, B, C} 에 속한다.
샘플 입력 Sample Input
3
샘플 출력 Sample Output
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

<span style="font-size:18px;">#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<queue>
#include<set>
#include<cmath>
#include<bitset>
#define mem(a,b) memset(a,b,sizeof(a))
#define lson i<<1,l,mid
#define rson i<<1|1,mid+1,r
#define llson j<<1,l,mid
#define rrson j<<1|1,mid+1,r
#define INF 1000000007
#define seed 13131
#define seed1 1313
#define maxn 20
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
#define step = 0
void Move(char from, char to, char help, int  num)
{
    printf("%d from %c to %c
",num,from,to,help);
}
void Hanoi(char from,char to,char help,int  num)
{
    if(num==1) {Move(from,to,help,1);return;}
    Hanoi(from,help,to,num-1);
    Move(from,to,help,num);
    Hanoi(help,to,from,num-1);
}
main()
{
    int num;
    scanf("%d",&num);
    printf("%d
",(1<<num)-1);
    Hanoi('A','C','B',num);
    return 0;
}
</span>