UVa101

Posted on In , Views:

題目:
https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=37

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include <bits/stdc++.h>
using namespace std;

/*
題意
move a onto b：将a和b所在上方的方块先归位，再将a移到b所在柱子
move a over b：仅将a所在上方的方块先归位，再将a移到b所在柱子
pile a onto b：将b所在上方的方块先归位，再将a及其上方的所有方块移到b所在柱子
pile a over b：无需归位，直接将a及其上方的所有方块移到b所在柱子
> move: a歸位
> onto: b歸位

quit：结束，打印输出
无效指令：命令中a和b在同一柱子，直接忽略即可
*/

bool illegal(vector<int> pos, int a, int b){
    if(a == b) return true;
    if(pos[a] == pos[b]) return true;

    return false;
}

void return_above(vector<stack<int>> &v, vector<int> &pos, int x){
    int pile_x = pos[x]; // x所在的柱子
    while(v[pile_x].top() != x){ // 將x以上的全部返回
        int block_above = v[pile_x].top();
        v[pile_x].pop();

        v[block_above].push(block_above);
        pos[block_above] = block_above;
    }
}

stack<int> move_from(vector<stack<int>> &v, vector<int> &pos, int x){
    stack<int> st;
    int pile_x = pos[x]; // x所在的柱子
    while(v[pile_x].top() != x){
        st.push(v[pile_x].top());
        v[pile_x].pop();
    }
    st.push(v[pile_x].top());
    v[pile_x].pop();

    return st;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n; // numbers of blocks
    cin >> n >> ws;

    vector<stack<int>> v(n);
    for(int i=0; i<n; ++i){
        v[i].push(i);
    }

    vector<int> pos(n); // 用pos來追蹤各個block的所在位置
    for(int i=0; i<n; ++i){
        pos[i] = i;
    }

    string input;
    while(getline(cin, input)){
        if(input == "quit") break;
        stringstream ss(input);
        string op1, op2;
        int a, b;
        ss >> op1 >> a >> op2 >> b;

        int pile_a = pos[a];
        int pile_b = pos[b];
        if(illegal(pos, a, b)) continue;

        if(op1 == "move"){
            return_above(v, pos, a);
        }
        if(op2 == "onto"){
            return_above(v, pos, b);
        }
        stack<int> tmp = move_from(v, pos, a);
        while(!tmp.empty()){
            v[pile_b].push(tmp.top());
            pos[tmp.top()] = pile_b;
            tmp.pop();
        }
    }

    for(int i=0; i<n; ++i){
        cout << i << ':';
        stack<int> tmp; // 輸出是從底到頂輸出，所以我要把他reverse
        while(!v[i].empty()){
            tmp.push(v[i].top());
            v[i].pop();
        }
        while(!tmp.empty()){
            cout << ' ' << tmp.top();
            tmp.pop();
        }
        cout << '\n';
    }

    return 0;
}