木塊問題（The Blocks Problem，Uva 101）
不定長數組：vector
vector就是一個不定長數組。不僅如此，它把一些常用操作“封裝”在了vector類型內部。 例如，若a是一個vector，可以用a.size( )讀取它的大小，a.resize( )改變大小，a.push_back( )向 尾部添加元素，a.pop_back( )刪除最后一個元素。
vector是一個模板類，所以需要用vectora或者vectorb這樣的方式來聲明一 個vector。Vector是一個類似于inta[]的整數數組，而vector就是一個類似于 stringa[ ]的字符串數組。vector看上去像是“一等公民”，因為它們可以直接賦值，還可以作為 函數的參數或者返回值，而無須像傳遞數組那樣另外用一個變量指定元素個數。（n=strlen(a);）
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
木塊問題（The Blocks Problem，Uva 101）
從左到右有n個木塊，編號為0～n-1，要求模擬以下4種操作（下面的a和b都是木塊編 號）。
- move a onto b: 把a和b上方的木塊全部放回初始的位置，然后把a放到b上面
- move a over b: 把a上方的木塊全部放回初始的位置，然后把a放在b所在木塊堆的最上方
- pile a onto b: 把b上方的木塊部放回初始的位置，然后把a和a上面所有的木塊整體放到b上面
- pile a over b: 把a和a上面所有的木塊整體放在b所在木塊堆的最上方
一組數據的結束標志為"quit"，如果有非法指令(a和b在同一堆)，應當忽略。
輸出:所有操作輸入完畢后，從左到右，從下到上輸出每個位置的木塊編號。
#include<iostream> #include<cstdio> #include<string> #include<vector> using namespace std; int n; vector<int> pile[30]; void find_block(int x,int &xp,int &j){ for(int i=0;i<n;i++){ for(j=0;j<pile[i].size();j++){ if(pile[i][j]==x) { xp=i; return; } } } } //把第p堆高度為h的木塊上方的所有木塊移回原位 void clear_above(int p,int h){ for(int i=h+1;i<pile[p].size();i++){ int x=pile[p][i]; pile[x].push_back(x); } pile[p].resize(h+1); } //把第p堆高度為h及其上方的木塊整體移動到p2 堆的頂部 void pile_onto(int p,int h,int p2){ for(int i=h;i<pile[p].size();i++){ pile[p2].push_back(pile[p][i]); } pile[p].resize(h); } //print void print(){ for(int i=0;i<n;i++){ printf("%d:",i); for(int j=0;j<pile[i].size();j++) printf(" %d",pile[i][j]); printf("\n"); } } int main(){ int a,b; string s1,s2; cin>>n; for(int i=0;i<n;i++) pile[i].push_back(i); while(1){ cin>>s1; if(!s1.compare("quit")) break; cin>>a>>s2>>b; int pa,pb,ha,hb; find_block(a,pa,ha); find_block(b,pb,hb); if(pa==pb) continue;//在同一堆，忽略 if(!s2.compare("onto")) clear_above(pb,hb); if(!s1.compare("move")) clear_above(pa,ha); pile_onto(pa,ha,pb); } print(); return 0; }
數據結構的核心是vectorpile[maxn]，所有操作都是圍繞它進行的。vector就像一個 二維數組，只是第一維的大小是固定的（不超過maxn），但第二維的大小不固定。上述代碼 還有一個值得學習的技巧：輸入一共有4種指令，但如果完全獨立地處理各指令，代碼就會 變得冗長而且易錯。更好的方法是提取出指令之間的共同點，編寫函數以減少重復代碼。
vector頭文件中的vector是一個不定長數組，可以用clear( )清空，resize( ) 改變大小，用push_back( )和pop_back( )在尾部添加和刪除元素，用empty( )測試是否為 空。vector之間可以直接賦值或者作為函數的返回值，像是“一等公民”一樣。
浙公網安備 33010602011771號