Posted on 2008-03-31 18:51
superman 阅读(668)
评论(0) 编辑 收藏 引用 所属分类:
ZOJ
1 /* Accepted 1011 C++ 00:00.00 988K */
2 #include <iostream>
3
4 using namespace std;
5
6 int n, m, k;
7 struct TransitionTable
8 {
9 int lSingal, rSingal;
10 TransitionTable * next;
11
12 void insert(int l, int r)
13 {
14 while(next)
15 {
16 next -> insert(l, r);
17 return;
18 }
19 TransitionTable * p = new TransitionTable;
20 p -> lSingal = l;
21 p -> rSingal = r;
22 p -> next = NULL;
23 next = p;
24 }
25
26 void clear()
27 {
28 TransitionTable *p = next;
29 TransitionTable *q;
30 while(p)
31 {
32 q = p;
33 p = p -> next;
34 delete q;
35 }
36 next = NULL;
37 }
38 }tranT[15][10];
39
40 void readTable()
41 {
42 int l, r;
43 for(int i = 0; i < n; i++)
44 for(int j = 0; j < k; j++)
45 while(1)
46 {
47 cin >> l >> r;
48 tranT[i][j].insert(l, r);
49 if(cin.get() == '\n')
50 break;
51 }
52 }
53
54 int L;
55 struct BinTree
56 {
57 char transmittingElement;
58 int left, right;
59 }Tree[2048 + 1];
60
61 void readTree()
62 {
63 char transmittingElement;
64 for(int i = 1; i <= (1 << (L + 1)) - 1; i++)
65 {
66 cin >> transmittingElement;
67 if(transmittingElement == '*')
68 {
69 Tree[i].transmittingElement = -1;
70 Tree[i / 2].left = Tree[i / 2].right = 0;
71 }
72 else
73 {
74 Tree[i].transmittingElement = transmittingElement - 'a';
75 if(i % 2 == 0)
76 Tree[i / 2].left = i;
77 else
78 Tree[i / 2].right = i;
79 }
80 }
81 }
82
83 int isValid[2048 + 1][15];
84
85 int PreOrder(int cur, int singal)
86 {
87 if(isValid[cur][singal])
88 return isValid[cur][singal];
89 TransitionTable * p = tranT[singal][Tree[cur].transmittingElement].next;
90 if(Tree[cur].left == 0 && Tree[cur].right == 0)
91 {
92 while(p)
93 {
94 if(p -> lSingal >= n - m && p -> rSingal >= n - m)
95 return isValid[cur][singal] = 1;
96 p = p -> next;
97 }
98 return isValid[cur][singal] = -1;
99 }
100
101 while(p)
102 {
103 if(PreOrder(cur * 2, p -> lSingal) == 1 && PreOrder(cur * 2 + 1, p -> rSingal) == 1)
104 return isValid[cur][singal] = 1;
105 p = p -> next;
106 }
107 return isValid[cur][singal] = -1;
108 }
109
110 int main()
111 {
112 int NTA = 0;
113 cin >> n >> m >> k;
114 while(true)
115 {
116 cout << "NTA" << ++NTA << ':' << endl;
117
118 readTable();
119 while(cin >> L)
120 {
121 if(L == -1)
122 break;
123 readTree();
124
125 if(PreOrder(1, 0) == 1)
126 cout << "Valid" << endl;
127 else
128 cout << "Invalid" << endl;
129
130 for(int i = 1; i <= (1 << (L + 1)) - 1; i++)
131 Tree[i].transmittingElement = Tree[i].left = Tree[i].right = 0;
132 memset(isValid, 0, sizeof(isValid));
133 }
134
135 for(int i = 0; i < n; i++)
136 for(int j = 0; j < k; j++)
137 tranT[i][j].clear();
138
139 cin >> n >> m >> k;
140 if(n == 0 && m == 0 && k == 0)
141 break;
142 else
143 cout << endl;
144 }
145
146 return 0;
147 }
148