nyoj 93-汉诺塔（三） stack

93-汉诺塔（三）

内存限制:64MB 时间限制:3000ms 特判: No
通过数:9 提交数:10 难度: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

样例输入:

样例输出:

legal
illegal
illegal

C/C++ AC：

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cstring>
 4 #include <cstdio>
 5 #include <cmath>
 6 #include <stack>
 7 #include <set>
 8 #include <map>
 9 #include <queue>
10 #include <climits>
11 
12 using namespace std;
13 const int MAX = 1e6 + 10;
14 int n, a, b;
15 
16 int main()
17 {
18     cin >>n;
19     while (n --)
20     {
21         scanf("%d%d", &a, &b);
22         stack <int> s[4];
23         for(int i = a; i >= 1; -- i)
24             s[1].push(i);
25         bool flag = true; // true legal
26         while (b --)
27         {
28             int mv1, mv2;
29             scanf("%d%d", &mv1, &mv2);
30             if (!flag) continue;
31             if (s[mv1].empty())
32             {
33                 flag = false;
34                 continue;
35             }
36             if (!s[mv2].empty() && s[mv1].top() > s[mv2].top())
37             {
38                 flag = false;
39                 continue;
40             }
41             s[mv2].push(s[mv1].top());
42             s[mv1].pop();
43         }
44         if (flag)
45             printf("legal
");
46         else
47             printf("illegal
");
48     }
49 }

思路来源