UVa101 - The Blocks Problem

  

   

    

     

    
    

     

      //UVa101 - The Blocks Problem
     
    
   

    

     

    
    

     

      #include<iostream>
     
    
   

    

     

    
    

     

      #include<cstdio>
     
    
   

    

     

    
    

     

      #include<string>
     
    
   

    

     

    
    

     

      #include<vector>
     
    
   

    

     

    
    

     

      using namespace std;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      const int maxn = 30;
     
    
   

    

     

    
    

     

      int n;
     
    
   

    

     

    
    

     

      vector<int>pile[maxn];
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      //找木块a所在的pile和height，以引用的形式返回调用者
     
    
   

    

     

    
    

     

      void find(int a, int &p, int &h){
     
    
   

    

     

    
    

     
    for(p = 0; p < n; p++)
     
    
   

    

     

    
    

     
        for(h = 0; h < pile[p].size(); h++)
     
    
   

    

     

    
    

     
            if(pile[p][h] == a) return;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      //把p堆高度为h的木块上方的所有木块移回原位
     
    
   

    

     

    
    

     

      void back(int p, int h){
     
    
   

    

     

    
    

     
    for(int i = h+1; i < pile[p].size(); i++){
     
    
   

    

     

    
    

     
        int b = pile[p][i];
     
    
   

    

     

    
    

     

              pile[b].push_back(b);
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     

          pile[p].resize(h+1);
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      //把p堆高度为h及其上方的木块整体移动到p2的顶部
     
    
   

    

     

    
    

     

      void doing(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);
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int main(){
     
    
   

    

     

    
    

     
    int a, b;
     
    
   

    

     

    
    

     

          cin >> n;
     
    
   

    

     

    
    

     

          string s1, s2;
     
    
   

    

     

    
    

     
    for(int i = 0; i < n; i++) pile[i].push_back(i);
     
    
   

    

     

    
    

     
    while(cin >> s1 && s1 != "quit"){
     
    
   

    

     

    
    

     

              cin >> a >> s2 >> b;
     
    
   

    

     

    
    

     
        int pa, pb, ha, hb; 
     
    
   

    

     

    
    

     
        find(a, pa, ha);
     
    
   

    

     

    
    

     
        find(b, pb, hb);
     
    
   

    

     

    
    

     
        if(pa == pb) continue;
     
    
   

    

     

    
    

     
        if(s2 == "onto") back(pb, hb);
     
    
   

    

     

    
    

     
        if(s1 == "move") back(pa, ha);
     
    
   

    

     

    
    

     
        doing(pa, ha, pb);
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     
    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");
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     
    return 0;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      /*
     
    
   

    

     

    
    

     

      10
     
    
   

    

     

    
    

     

      move 9 onto 1
     
    
   

    

     

    
    

     

      move 8 over 1
     
    
   

    

     

    
    

     

      move 7 over 1
     
    
   

    

     

    
    

     

      move 6 over 1
     
    
   

    

     

    
    

     

      pile 8 over 6
     
    
   

    

     

    
    

     

      pile 8 over 5
     
    
   

    

     

    
    

     

      move 2 over 1
     
    
   

    

     

    
    

     

      move 4 over 9
     
    
   

    

     

    
    

     

      quit
     
    
   

    

     

    
    

     

      
     
    
   

    

     

    
    

     

      0: 0
     
    
   

    

     

    
    

     

      1: 1 9 2 4
     
    
   

    

     

    
    

     

      2:
     
    
   

    

     

    
    

     

      3: 3
     
    
   

    

     

    
    

     

      4:
     
    
   

    

     

    
    

     

      5: 5 8 7 6
     
    
   

    

     

    
    

     

      6:
     
    
   

    

     

    
    

     

      7:
     
    
   

    

     

    
    

     

      8:
     
    
   

    

     

    
    

     

      9:
     
    
   

    

     

    
    

     

      */
     
    
  
 

文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。

原文链接：gwj1314.blog.csdn.net/article/details/55693958