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

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

梦里梦外; 2022-11-27 03:22 196阅读 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;
}