a632 - 12. Domino Rally
題目描述
題目描述了一種骨牌移除遊戲。給定一串骨牌，每個骨牌有編號和方向（正向或反向）。遊戲規則是從左到右尋找相鄰的骨牌，如果它們連接的點數相同，則移除它們。重複此過程，直到無法再移除任何骨牌。目標是輸出剩餘的骨牌編號，或者如果所有骨牌都被移除，則輸出 "DATASET CLEARED"。
解題思路
這個問題可以使用貪婪演算法來解決。我們從左到右遍歷骨牌，尋找可以移除的相鄰骨牌對。如果找到一對，則移除它們並重置遍歷到最左邊。重複此過程，直到無法再找到可移除的骨牌對。
程式碼使用一個二維陣列 all 來儲存骨牌的編號和方向。dies 陣列用於根據骨牌編號和方向獲取連接的點數。程式碼首先讀取骨牌序列，然後進入主迴圈，不斷嘗試移除骨牌。如果成功移除一對骨牌，則將它們的編號設為 -1，並重置遍歷索引。如果無法找到可移除的骨牌對，則檢查是否所有骨牌都被移除，並輸出相應的結果。
複雜度分析
- 時間複雜度: O(n^2)，其中 n 是骨牌的數量。在最壞的情況下，我們可能需要遍歷所有骨牌的所有可能的配對。
- 空間複雜度: O(n)，其中 n 是骨牌的數量。我們使用
all陣列來儲存骨牌的資訊。
程式碼
#include <iostream>
using namespace std;
int dies[29][2],all[29][2],n,t,l;
char way;
int main(){
for(int i=0,c=0;i<=6;++i){
for(int j=i;j<=6;++j){
++c;
dies[c][0]=i;
dies[c][1]=j;
}
}
while(cin >> t){
cin >> way;
if(t){
all[n][0]=t;
if(way=='B')all[n][1]=1;
++n;
}
else{
bool ans(0);
int ii(0),j;
while(ii!=n-1){
bool ca(0);
for(;ii<n;++ii){
if(all[ii][0]!=-1){
l=dies[all[ii][0]][1-all[ii][1]];
ca=1;
break;
}
}
if(!ca){
ans=1;
break;
};
for(j=ii+1;j<n;++j){
if(all[j][0]!=-1){
if(l==dies[all[j][0]][all[j][1]]){
all[ii][0]=-1;
all[j][0]=-1;
ii=0;
j=n;
}
else{
++ii;
j=n;
}
}
}
if(j==n)break;
}
if(ans)
cout << "DATASET CLEARED\n";
else{
for(int i=0;i<n;++i)
if(all[i][0]!=-1)
cout << all[i][0] << " ";
cout << "\n";
}
n=0;
for(int i=0;i<29;++i){
all[i][0]=0;
all[i][1]=0;
}
}
}
}