2011-06-15 07:27:59Morris
c073. The Blocks Problem
http://zerojudge.tw/ShowProblem?problemid=c073
內容 ：
在早期人工智慧的領域中常常會用到機器人，在這個問題中有一支機器手臂接受指令來搬動積木，而你的任務就是輸出最後積木的情形。
一開始在一平坦的桌面上有n塊積木（編號從0到n-1）0號積木放在0號位置上，1號積木放在1號位置上，依此類推，如下圖。
機器手臂有以下幾種合法搬積木的方式（a和b是積木的編號）：
- move a onto b
在將a搬到b上之前，先將a和b上的積木放回原來的位置（例如：1就放回1的最開始位罝） - move a over b
在將a搬到b所在的那堆積木之上之前，先將a上的積木放回原來的位罝（b所在的那堆積木不動） - pile a onto b
將a本身和其上的積木一起放到b上，在搬之前b上方的積木放回原位 - pile a over b
將a本身和其上的積木一起搬到到b所在的那堆積木之上 - quit
動作結束
前四個動作中若a=b，或者a, b在同一堆積木中，那麼這樣的動作算是不合法的。所有不合法的動作應該被忽略，也就是對各積木均無改變。
輸入說明 ：
輸入含有多組測試資料，每組測試資料的第一列有一個正整數n（0 < n < 25），代表積木的數目（編號從0到n-1）。接下來為機器手臂的動作，每個動作一列。如果此動作為 quit ，代表此組測試資料輸入結束。你可以假設所有的動作都符合上述的樣式。請參考Sample Input。
輸出說明 ：
每組測試資料輸出桌面上各位置積木的情形（每個位置一列，也就是共有n列），格式請參考Sample Output。
範例輸入 ：
10move 9 onto 1move 8 over 1move 7 over 1move 6 over 1pile 8 over 6pile 8 over 5move 2 over 1move 4 over 9quit4pile 0 over 1pile 2 over 3move 1 onto 3quit
範例輸出 ：
0: 01: 1 9 2 42:3: 34:5: 5 8 7 66:7:8:9:0: 01:2: 23: 3 1
提示 ：
出處 ：
ACM 101
作法 : 模擬題
寫到都快昏了
作法 : 模擬題
/**********************************************************************************/
/* Problem: c073 "The Blocks Problem" from ACM 101 */
/* Language: C */
/* Result: AC (6ms, 272KB) on ZeroJudge */
/* Author: morris1028 at 2011-06-13 20:30:46 */
/**********************************************************************************/
#include<stdio.h>
#include<string.h>
main() {
int n, a, b, ta, tb;
char s1[5], s2[5];
while(scanf("%d", &n) == 1) {
int set[25] = {}, block[25][25] = {}, bt[25] = {};
for(a = 0; a < n; a++)/*init*/
set[a] = a, block[a][0] = a;
while(scanf("%s", s1) == 1) {
if(s1[0] == 'q') /*quit*/
break;
scanf("%d %s %d", &ta, s2, &tb);
if(ta == tb || set[ta] == set[tb]) continue;
if(s1[0] == 'm') {/*move*/
if(s2[1] == 'n') {/*onto*/
for(a = bt[set[ta]]; block[set[ta]][a] != ta; a--, bt[set[ta]]--)
block[block[set[ta]][a]][++bt[block[set[ta]][a]]] = block[set[ta]][a],
set[block[set[ta]][a]] = block[set[ta]][a];
for(a = bt[set[tb]]; block[set[tb]][a] != tb; a--, bt[set[tb]]--)
block[block[set[tb]][a]][++bt[block[set[tb]][a]]] = block[set[tb]][a],
set[block[set[tb]][a]] = block[set[tb]][a];
block[set[tb]][++bt[set[tb]]] = ta, bt[set[ta]]--, set[ta] = set[tb];
}
else {/*over*/
for(a = bt[set[ta]]; block[set[ta]][a] != ta; a--, bt[set[ta]]--)
block[block[set[ta]][a]][++bt[block[set[ta]][a]]] = block[set[ta]][a],
set[block[set[ta]][a]] = block[set[ta]][a];
block[set[tb]][++bt[set[tb]]] = ta, bt[set[ta]]--, set[ta] = set[tb];
}
}
else { /*pile*/
if(s2[1] == 'n') {/*onto*/
for(a = bt[set[tb]]; block[set[tb]][a] != tb; a--, bt[set[tb]]--)
block[block[set[tb]][a]][++bt[block[set[tb]][a]]] = block[set[tb]][a],
set[block[set[tb]][a]] = block[set[tb]][a];
for(a = bt[set[ta]]; block[set[ta]][a] != ta; a--) ;
int in = a, tin = bt[set[ta]], sset = set[ta];
for(a = in; a <= tin; a++, bt[sset]--)
block[set[tb]][++bt[set[tb]]] = block[sset][a], set[block[sset][a]] = set[tb];
}
else {
for(a = bt[set[ta]]; block[set[ta]][a] != ta; a--) ;
int in = a, tin = bt[set[ta]], sset = set[ta];
for(a = in; a <= tin; a++, bt[sset]--)
block[set[tb]][++bt[set[tb]]] = block[sset][a], set[block[sset][a]] = set[tb];
}
}
}
for(a = 0; a < n; a++) {
printf("%d:", a);
for(b = 0; b <= bt[a]; b++)
printf(" %d",block[a][b]);
puts("");
}
}
return 0;
}