STL初步：不定长数组vector(木块问题（The Blocks Problem))

梦里梦外; 2022-11-27 03:22 109阅读 0赞

从左到右有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及其上方的木块整体摞在b上面
 *  pile a over b：把a及其上方的木块整体摞在b所在堆的顶部

遇到quit时终止一组数据。a和b在同一堆的指令是非法指令，应当忽略。所有操作结束后，输出每个位置的木块列表，按照从底部到顶部的顺序排列。  
**分析**  
每个木块堆的高度不确定，用vector保存很合适；木块堆的个数不超过n，用一个数组来存就可以了。

#include<cstdio>
    #include<string>
    #include<vector>
    #include<iostream>
    using namespace std;
    const int maxn=30;
    int n;
    vector<int> pile[maxn];  //每个pile是一个vector
    void find_block(int a,int &p,int &h)//找木块a所在的pile和weight,以引用的形式返回调用者
    { 
     for(p=0;p<n;p++)
     { 
      for(h=0;h<pile[p].size();h++)
      { 
       if(pile[p][h]==a)
       { 
        return;
       }
      }
     }
    }
    void clear_above(int p,int h) //把第p堆高度为h的木块上方的所有木块移回原位 
    { 
     for(int i=h+!;i<pile[p].size();i++)
     { 
      int b=pile[p][i];
      pile[b].push_back(b); //把木块b放回原位 
     }
     pile[p].resize(h+1);  //pile应只保留下标0~h的元素 
     } 
    void pile_onto(int p,int h,int p2) //把第p堆高度为h的及其上方的木块上整体移动到p2堆的顶部 
      for(int i=h;i<pile[p].size();i++)
      { 
       pile.push_back(pile[p][i]);
     }
     pile[p].resize(h); 
    }
    void print()
    { 
     for(int i=0;i<n;i++)
     { 
      printf("%d:",i);
      for(itn j=0;j<pile[i].size();j++)
      { 
       printf(" %d",pile[i][j]);
       printf("\n");
      }
     }
    } 
    int main()
    { 
     int a,b=0;
     cin>>n;
     string s1,s2;
     for(int i=0;i<n;i++)
     { 
      pile.push_back(i);
     }
     while(cin>>s1>>a>>s2>>b)
     { 
      int pa,pb,ha,hb;
      find_block(a,pa,ha);
      find_block(b,pb,hb);
      if(pa==pb)  //非法指令 
      { 
       continue;
      }
      if(s2=="onto")
      { 
       clear_above(pb,hb);
       } 
      if(s1=="move")
      { 
       clear_above(pa,ha);
      }
      pile_onto(pa,ha,pb);
     }
     printf();
     return 0;
    }

vector像一个二维数组，第一维大小固定（不超过maxn),第二维大小不固定。  
vector可用push\_back()和pop\_back()在尾部添加和删除元素，用clear()清空，resize()改变大小，用empty测试是否为空。  
vector可以直接赋值或者作为函数的返回值。