[UVa] 101 - The Blocks Problem

參考算法競賽入門經典ㄧ書

運用STL中vector的一些特性

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <iostream>
#include <cctype>
#include <set>
#include <map>
#include <vector>
#include <sstream>
using namespace std;
int n;
vector<int> pile[30];
void find_block(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 clear_above(int p, int h){
  for(int i=h+1; i<pile[p].size();i++){
    int b = pile[p][i];
    pile[b].push_back(b); //put b back
  }
  pile[p].resize(h+1); //改變大小，只保留h以下
}
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]); //p堆高度h以上的移到p2
  pile[p].resize(h); //h-1以上的去除
}

int main(){
  scanf("%d",&n);
  int a,b;
  string s1,s2;
  for(int i=0;i<n;i++) pile[i].push_back(i) ; 
  while(cin >> s1){
    if(s1=="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; //ignore
    if(s2 == "onto")clear_above(pb,hb); //遇onto則b上方木塊全部歸位
    if(s1 == "move")clear_above(pa,ha); //遇move則a上方木塊全部歸位
    pile_onto(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;
}