算法入门课2总结

Bits
链接：https://ac.nowcoder.com/acm/problem/201605
参考来自Randolph的https://blog.nowcoder.net/n/4eb42e3cb78c46108488fff872d55c78

#include<bits/stdc++.h>
using namespace std;

int t[3][12], cnt[3], n, m, width; 
/*
    t用来存储三个柱子上的编号
    假设有n个柱子
    则一开始的编号存储为 t[0][1] = n, t[0][2] = n - 1, t[0][2] = n - 2;
    因此推出 n - i + 1
    cnt用来存每个柱子上圆盘的数量
    width表示最大的圆盘的宽度
    n 表示圆盘的个数， m 表示整个图形的宽度
*/

string _begin, _str, str;
/*
    用_begin来存储第一行和第二行:
    ...................
    ...|.....|.....|...
    用_str来存储...|.....|.....|...
    之后用str来用圆盘对|进行替换
*/

void print() {
    for(int floor = n, pos, len; floor; floor--) { //由于从上往下进行输出，因此要从最高层往下走
        str = _str; //将...|.....|.....|...赋值给str
        for(int i = 0; i < 3; i++) {
            if(cnt[i] >= floor) {  //如果这个柱子上圆盘>=层数说明该层有柱子
                len = 2 * t[i][floor] + 1;  //该层柱子的长度
                pos = width * i + i + 1 + (width - len) / 2;//起始位置
                for(int j = pos; j < pos + len; j++)
                    str[j] = '*';
            }
        }
        cout << str << "\n";
    }
}

void move(int a, int b) {  //将a挪到b
    t[b][++cnt[b]] = t[a][cnt[a]--]; //b的层数+1 = a的层数的盘子
    cout << _begin ;
    print();
}

void hanoi(int a, int b, int x) {
    if(x == 1) {
        move(a, b);
        return;
    }
    hanoi(a, 3 - a - b, x - 1);  //3 - a - b是中转柱子
    move(a, b);
    hanoi(3 - a - b, b, x - 1);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    m = 6 * n + 7;
    for(int i = 1; i <= n; i++) t[0][i] = n - i + 1;
    cnt[0] = n;
    for(int i = 0; i < m; i++) _begin += ".", _str += ".";
    width = 2 * n + 1;
    _str[width / 2 + 1] = _str[width + width / 2 + 2] = _str[width * 2 + width / 2 + 3] = '|';  
    _begin += "\n" + _str + "\n";
    cout << _begin;
    print();
    string tmp;  //tmp来存储后三行
    for(int i = 0; i < m; i++) tmp += '-';
    _begin = tmp + "\n" + _begin;
    if(n & 1) hanoi(0, 1, n);
    else hanoi(0, 2, n);
    return 0; 
}