日期：2026年2月15日
ZeroJudge 題目連結：c073. 00101 - The Blocks Problem
解題想法
指令有以下 5 種，其中 a 和 b 是積木的編號：
- move a onto b: 先將 a 和 b 上方的積木放回原來的位置，再將 a 移到 b 上方。
- move a over b: 先將 a 上方的積木放回原來的位罝，b 所在的那堆積木不動，再將 a 移到 b 上方。
- pile a onto b: 先將 b 上方的積木放回原位，再將 a 本身及上方的積木一起放到 b 上方。
- pile a over b: 將 a 本身和上方的積木一起搬到到 b 所在的那堆積木上方。
- quit: 動作結束，印出結果。
initial: [[0], [1], [2], [3], [4], [5], [6], [7], [8], [9]]
move 9 onto 1: [[0], [1, 9], [2], [3], [4], [5], [6], [7], [8], []]
move 8 over 1: [[0], [1, 9, 8], [2], [3], [4], [5], [6], [7], [], []]
move 7 over 1: [[0], [1, 9, 8, 7], [2], [3], [4], [5], [6], [], [], []]
move 6 over 1: [[0], [1, 9, 8, 7, 6], [2], [3], [4], [5], [], [], [], []]
pile 8 over 6: [[0], [1, 9, 8, 7, 6], [2], [3], [4], [5], [], [], [], []] # 8, 6 在同一疊，無效
pile 8 over 5: [[0], [1, 9], [2], [3], [4], [5, 8, 7, 6], [], [], [], []]
move 2 over 1: [[0], [1, 9, 2], [], [3], [4], [5, 8, 7, 6], [], [], [], []]
move 4 over 9: [[0], [1, 9, 2, 4], [], [3], [], [5, 8, 7, 6], [], [], [], []]
範例測資 2，$n = 4$，初始及每次操作後的狀態分別為
initial: [[0], [1], [2], [3]]
pile 0 over 1: [[], [1, 0], [2], [3]]
pile 2 over 3: [[], [1, 0], [], [3, 2]]
move 1 onto 3: [[0], [], [2], [3, 1]]
Python 程式碼
使用時間約為 7 ms，記憶體約為 3.1 MB，通過測試。
import sys
for line in sys.stdin:
n = int(line)
piles = [[i] for i in range(n)] # 每一疊的木塊編號
pos = [i for i in range(n)] # 每個編號的木塊各在第幾疊
for line in sys.stdin:
if line.rstrip() == "quit":
for i, pile in enumerate(piles):
print(f"{i:d}: ", end="")
print(*pile)
break
command = list(line.split())
a, b = int(command[1]), int(command[3])
if pos[a] == pos[b]: continue # a, b 在同一疊，不合法的指令
if command[0] == "move":
if command[2] == "onto":
while piles[pos[a]][-1] != a: # 檢查 a 所在的那一疊上方
c = piles[pos[a]].pop() # 取出並移除最上方的木塊編號為 c
pos[c] = c # 把 c 歸位
piles[c].append(c)
while piles[pos[b]][-1] != b: # 檢查 b 所在的那一疊上方
c = piles[pos[b]].pop() # 取出並移除最上方的木塊編號為 c
pos[c] = c # 把 c 歸位
piles[c].append(c)
piles[pos[b]].append(piles[pos[a]].pop()) # 將 a 移到 b 所在那一疊上方
pos[a] = pos[b] # a 的位置改成 b 所在的位置
elif command[2] == "over":
while piles[pos[a]][-1] != a: # 檢查 a 所在的那一疊上方
c = piles[pos[a]].pop() # 取出並移除最上方的木塊編號為 c
pos[c] = c # 把 c 歸位
piles[c].append(c)
piles[pos[b]].append(piles[pos[a]].pop()) # 將 a 移到 b 所在那一疊上方
pos[a] = pos[b] # a 的位置改成 b 所在的位置
elif command[0] == "pile":
if command[2] == "onto":
while piles[pos[b]][-1] != b: # 檢查 b 所在的那一疊上方
c = piles[pos[b]].pop() # 取出並移除最上方的木塊編號為 c
pos[c] = c # 把 c 歸位
idx = piles[pos[a]].index(a) # 找出 a 在這一疊的索引值
sub = piles[pos[a]][idx:] # 取出 idx 之後的項目
piles[pos[a]] = piles[pos[a]][:idx] # 移除 idx 之後的項目
for d in sub: # 修改 a 及上方積木的位置
pos[d] = pos[b] # 改成 b 所在的位置
piles[pos[b]] += sub # 將 a 及上方的積木移到 b 所在那一疊上方
elif command[2] == "over":
idx = piles[pos[a]].index(a) # 找出 a 在這一疊的索引值
sub = piles[pos[a]][idx:] # 取出 idx 之後的項目
piles[pos[a]] = piles[pos[a]][:idx] # 移除 idx 之後的項目
for d in sub: # 修改 a 及上方積木的位置
pos[d] = pos[b] # 改成 b 所在的位置
piles[pos[b]] += sub # 將 a 及上方的積木移到 b 所在那一疊上方
C++ 程式碼
使用時間約為 1 ms，記憶體約為 328 kB，通過測試。
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int n;
while(cin >> n) {
vector<vector<int>> piles (n, vector<int> (1)); // 每一疊的木塊編號
vector<int> pos (n); // 每個編號的木塊各在第幾疊
for(int i=0; i<n; i++) {
piles[i][0] = i;
pos[i] = i;
}
string cmd1, cmd2;
int a, b;
while(cin >> cmd1) {
if (cmd1 == "quit") {
for(int i=0; i<n; i++) {
cout << i << ": ";
if (piles[i].empty()) {
cout << "\n";
continue;
}
for(int j=0; j<(int)piles[i].size(); j++) {
cout << piles[i][j] << " \n"[j == (int)piles[i].size()-1];
}
}
break;
}
cin >> a >> cmd2 >> b;
if (pos[a] == pos[b]) continue; // a, b 在同一疊，不合法的指令
if (cmd1 == "move") {
if (cmd2 == "onto") {
while(piles[pos[a]].back() != a) { // 檢查 a 所在的那一疊上方
int c = piles[pos[a]].back(); // 取出並移除最上方的木塊編號為 c
piles[pos[a]].pop_back();
pos[c] = c; // 把 c 歸位
piles[c].push_back(c);
}
while(piles[pos[b]].back() != b) { // 檢查 b 所在的那一疊上方
int c = piles[pos[b]].back(); // 取出並移除最上方的木塊編號為 c
piles[pos[b]].pop_back();
pos[c] = c; // 把 c 歸位
piles[c].push_back(c);
}
piles[pos[b]].push_back(piles[pos[a]].back()); // 將 a 移到 b 所在那一疊上方
piles[pos[a]].pop_back();
pos[a] = pos[b]; // a 的位置改成 b 所在的位置
} else if (cmd2 == "over") {
while(piles[pos[a]].back() != a) { // 檢查 a 所在的那一疊上方
int c = piles[pos[a]].back(); // 取出並移除最上方的木塊編號為 c
piles[pos[a]].pop_back();
pos[c] = c; // 把 c 歸位
piles[c].push_back(c);
}
piles[pos[b]].push_back(piles[pos[a]].back()); // 將 a 移到 b 所在那一疊上方
piles[pos[a]].pop_back();
pos[a] = pos[b]; // a 的位置改成 b 所在的位置
}
} else if (cmd1 == "pile") {
if (cmd2 == "onto") {
while(piles[pos[b]].back() != b) { // 檢查 b 所在的那一疊上方
int c = piles[pos[b]].back(); // 取出並移除最上方的木塊編號為 c
piles[pos[b]].pop_back();
pos[c] = c; // 把 c 歸位
}
vector<int> tmp; // 暫存從 a 所在這疊從最上面到 a 為止的資料
while(piles[pos[a]].back() != a) {
int c = piles[pos[a]].back();
piles[pos[a]].pop_back();
tmp.push_back(c);
}
tmp.push_back(piles[pos[a]].back()); // 最後要再處理一次，這項是 a
piles[pos[a]].pop_back();
while(!tmp.empty()) { // 從 tmp 最後面取出資料移到 b 所在那疊
int c = tmp.back();
tmp.pop_back();
piles[pos[b]].push_back(c);
pos[c] = pos[b];
}
} else if (cmd2 == "over") {
vector<int> tmp; // 暫存從 a 所在這疊從最上面到 a 為止的資料
while(piles[pos[a]].back() != a) {
int c = piles[pos[a]].back();
piles[pos[a]].pop_back();
tmp.push_back(c);
}
tmp.push_back(piles[pos[a]].back()); // 最後要再處理一次，這項是 a
piles[pos[a]].pop_back();
while(!tmp.empty()) { // 從 tmp 最後面取出資料移到 b 所在那疊
int c = tmp.back();
tmp.pop_back();
piles[pos[b]].push_back(c);
pos[c] = pos[b];
}
}
}
}
}
return 0;
}
沒有留言:
張貼留言