NYOJ 93 漢諾塔（三） （棧 stack）

• 題目93
• 題目資訊
• 運作結果
• 本題排行
• 讨論區

漢諾塔（三）

時間限制： 3000 ms  |  記憶體限制： 65535 KB 難度： 3

描述

在印度，有這麼一個古老的傳說：在世界中心貝拿勒斯（在印度北部）的聖廟裡，一塊黃銅闆上插着三根寶石針。印度教的主神梵天在創造世界的時候，在其中一根針上從下到上地穿好了由大到小的64片金片，這就是所謂的漢諾塔。不論白天黑夜，總有一個僧侶在按照下面的法則移動這些金片：一次隻移動一片，不管在哪根針上，小片必須在大片上面。僧侶們預言，當所有的金片都從梵天穿好的那根針上移到另外一根針上時，世界就将在一聲霹靂中消滅，而梵塔、廟宇和衆生也都将同歸于盡。

現在我們把三根針編号為1，2，3。

所有的金片在初始時都在1号針上，現在給你的任務是判斷一系列的指令過程中，是否會出現非法的指令。

而非法指令有以下兩種情況：

1、某個針上已經沒有金片了，但是指令依然要求從該處移動金片到其它針上。

2、把一個大的金片移動到了小的金片上。

輸入

第一行輸入一個整數N表示測試資料的組數(N<10)

每組測試資料的第一行有兩個整數P,Q(1<P<64,1<Q<100)，分别表示漢諾塔的層數與随後指令的條數

随後的Q行，每行都輸入兩個整數a,b，(1<=a,b<=3)表示一條指令。

指令1 2表示把1号針最上面的金片移動到2号針最上面。

資料保證a,b不會相同。

輸出

如果存在非法指令，請輸出illegal

不存在非法指令則輸出legal

樣例輸入

3
2 1
1 2
3 3
1 2
1 3
3 2
2 1
2 1      

樣例輸出

legal
illegal
illegal      

#include <iostream>
#include <stack>
using namespace std;
int n, p, q, a, b;
int flag;
int main()
{
    cin >> n;
    while (n--){
        flag = 1;
        stack<int> s[4];
        cin >> p >> q;
        for (int i = 1; i < 4; i++){
            while (!s[i].empty())
                s[i].pop();
        }
        for (int i = p; i > 0; i--)
            s[1].push(i);    //将所有金片初始在1号針上  
        for (int i = 0; i < q; i++){
            cin >> a >> b;
            if (s[a].empty()){    //非法指令1
                flag = 0;
                break;
            }
            if (!s[b].empty() && s[a].top() > s[b].top()){   //非法指令2
                flag = 0;
                break;
            }
            s[b].push(s[a].top());
            s[a].pop();
        }
        if (flag)
            cout << "legal" << endl;
        else
            cout << "illegal" << endl;
    }
    return 0;
}