alan23273850 的刷題筆記
c073: 00101 - The Blocks Problem
Tags: linked-list
出處：https://zerojudge.tw/ShowProblem?problemid=c073
提交：https://zerojudge.tw/Submissions?problemid=c073&account=allllllan123456
問題：給定 $n\in[1,24]$ 個初始積木堆，每一堆都先放置剛好一塊積木，而且該積木的序號就是所在積木堆的序號。接下來給你一些搬積木指令，這些指令只會是把 a 積木搬到 b 積木之上，但是其中又有分 a 上面的積木是要跟著一起搬還是要先復原到各自所屬的積木堆、也有分 b 上面的積木是否也要先復原到各自所屬的積木堆，因此總共有 4 種指令。請問搬完之後每一堆的積木狀況？
解法：這題也是蠻經典的資料結構題目，記錄在這邊只是想試試看用 array 模擬會寫得怎麼樣，後來覺得還是免不了要細心，建議每完成一次搬遷就按照固定的 attribute 順序先檢查誰會受到影響，再對那些受影響的積木去作更新，這樣做的好處是能確實檢查到必須更新的變數，不會有遺漏。我們用 group[.] 代表每塊積木屬於哪一堆，prev[.] 代表一塊積木的前一塊積木是誰，next[.] 代表一塊積木的下一塊積木是誰，tail[.] 代表每一堆積木的最後一塊是誰，因此只有 tail 的 index 是指積木堆，其他的 index 都是指積木塊。
1#include <bits/stdc++.h>
2using namespace std;
3
4int group[24], preV[24], nexT[24], last[24];
5
6void reset_all_blocks_after_x(int x) {
7 // group[x]: ... x ... j i
8 // i: ... (last[i])
9 // group[x]: ... x ... j
10 // i: ... (last[i]) i
11 int i = last[group[x]]; // x 所在堆的最後一個元素
12 while (i != x) {
13 int j = preV[i]; // 先保存前一個元素
14 group[i] = i;
15 preV[i] = last[i];
16 nexT[j] = -1;
17 if (last[i] != -1) nexT[last[i]] = i;
18 // last[group[x]] = j;
19 last[i] = i;
20 i = j; // 還原
21 }
22 nexT[x] = -1; last[group[x]] = x;
23}
24
25int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
26 int n, a, b; string str1, str2;
27 while (cin >> n) {
28 for (int i=0; i<n; i++)
29 group[i] = last[i] = i,
30 preV[i] = nexT[i] = -1;
31 while (cin >> str1 && str1!="quit") {
32 cin >> a >> str2 >> b;
33 if (group[a] == group[b]) continue;
34 if (str1 == "move") reset_all_blocks_after_x(a);
35 if (str2 == "onto") reset_all_blocks_after_x(b);
36 // group[a]: ... (preV[a]) {a ...}
37 // group[b]: ... last[group[b]]
38 // group[a]: ...
39 // group[b]: ... last[group[b]] {a ...}
40 nexT[preV[a]] = -1;
41 nexT[last[group[b]]] = a;
42 int temp = preV[a];
43 preV[a] = last[group[b]];
44 last[group[b]] = last[group[a]];
45 last[group[a]] = temp;
46 while (a != -1)
47 group[a] = group[b], a = nexT[a];
48 }
49 for (int i=0; i<n; i++) {
50 cout << i << ':';
51 int j = last[i];
52 while (j!=-1 && preV[j]!=-1) j = preV[j];
53 while (j != -1)
54 cout << ' ' << j, j = nexT[j];
55 cout << '\n';
56 }
57 }
58 return 0;
59}