c073 - 00101 - The Blocks Problem
題目描述
題目描述了一個積木搬運問題，需要模擬機器手臂根據指令移動積木，並最終輸出每個位置上的積木堆疊情況。輸入包含積木數量和一系列移動指令，指令包括 move a onto b、move a over b、pile a onto b、pile a over b 和 quit。需要處理非法指令（例如，a 和 b 在同一堆積木中或 a 等於 b），並在 quit 指令後輸出最終的積木堆疊狀態。
解題思路
本題的核心是模擬積木的堆疊和移動。可以使用多個棧來表示每個位置上的積木堆疊。fr[i] 陣列用於記錄積木 i 所屬的棧的頂部元素。b[i] 陣列表示每個棧，b[i].a 儲存棧中的積木，b[i].sz 儲存棧的大小。
對於每個指令，需要根據指令類型執行相應的操作：
move a onto b: 將a及其上面的積木移回原位，將b及其上面的積木移回原位，然後將a放到b上。move a over b: 將a及其上面的積木移回原位，然後將a放到b的上面。pile a onto b: 將a及其上面的積木直接放到b上。pile a over b: 將a及其上面的積木直接放到b的上面。
在執行指令之前，需要檢查指令是否合法。如果指令不合法，則忽略該指令。
複雜度分析
- 時間複雜度: O(n * m * k)，其中 n 是積木數量，m 是指令數量，k 是棧的最大大小。在最壞情況下，每次移動操作可能需要遍歷整個棧。
- 空間複雜度: O(n)，主要用於儲存棧和
fr陣列。
程式碼
#include <iostream>
using namespace std;
struct bx{
int a[30],sz;
};
bx b[30];
int n,x,y,fr[30];
string is,is2;
void ab(int tar){
int p=fr[tar],tp=b[p].a[b[p].sz-1];
while(tp!=tar){
fr[tp]=tp;
b[tp].a[b[tp].sz++]=tp;
b[p].sz--;
tp=b[p].a[b[p].sz-1];
}
}
void ot(int st,int tar){
int p1=fr[st],p2=fr[tar],nh=0;
bool has=0;
for(int i=0;i<b[p1].sz;++i){
if(has==0&&b[p1].a[i]==st){
has=1;
nh=i;
}
if(has){
fr[b[p1].a[i]]=p2;
b[p2].a[b[p2].sz++]=b[p1].a[i];
}
}
b[p1].sz=nh;
}
int main(){
while(cin >> n){
for(int i=0;i<n;++i){
b[i].a[0]=i;
b[i].sz=1;
fr[i]=i;
}
while(cin >> is){
if(is=="quit")break;
cin >> x >> is2 >> y;
if(fr[x]==fr[y])continue;
if(is=="move")ab(x);
if(is2=="onto")ab(y);
ot(x,y);
}
for(int i=0;i<n;++i){
cout << i << ":";
for(int j=0;j<b[i].sz;++j)
cout << " " << b[i].a[j];
cout << "\n";
}
}
}