UVa 101 The Blocks Problem 数据结构专题

101-The Blocks Problem

67864

19.16%

14194

题目链接：

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=103&page=show_problem&problem=37

题目类型： 数据结构， 二叉树

题意：

有N个位置， 编号为 0～N-1， 初始下，各个位置上放置这和位置编号相同的砖块，即砖块1，砖块2……砖块N-1。 然后有四种命令操作方式：

1.moveaontob :把砖a移动到砖b上面，如果a和b上面都有砖块，要先把它们放回原来位置。

2.move a over b: 把a移动到有b的“砖堆”上面，移动前需要把a上面的砖块都恢复到原位置，b的堆保持不变。

3.pileaontob：把a之上的（包括a）搬到b之上，要先把b上面的砖放回到原来位置

4.pileaoverb: 直接把a之上的（包括a）搬到b所在的“砖堆”上。

5.quit: 结束命令。

解体思路： 初刚看到时，想用stack模拟，但是这样操作会比较多，可能会TLE。 于是自己模拟写了类似栈的类，但是可以随机存储。 STL确实用起来比较方便，但是很不灵活。

#include<cstdio>
#include<iostream>
#include<string>
using namespace std;

int n, block_a, block_b, pos_a, pos_b;
string command1,command2;

class Pile{
public:
    Pile(){ index = 0; }
    void init_set(int a){
        index=0;
        arr[index++] = a;
    }
    int top(){
        return arr[index-1];
    }
    void add(int a){
        arr[index++] = a;
    }
    bool is_empty(){
        if(index==0)
            return true;
        return false;
    }
    int find(int a){
       for(int i=0; i<index; ++i){
           if(arr[i]==a)
               return i;
       }
       return -1;
    }
    void output(){
        if(index!=0){
            for(int i=0; i<index; ++i){
                printf(" %d",arr[i]);
            }
        }
    }
    int arr[100];
    int index;  
};

Pile arr[100];

// 找到砖块a所在的堆。 
int find_block(int a){
    int result;
    for(int i=0; i<n; ++i){
        result=arr[i].find(a);
        if(result!=-1) return i;
    }
}

// 把砖块a之上的砖块全都返回初始位置。pos时砖堆位置
void return_block(int pos, int a){
    if(arr[pos].top()==a) return;  
    int index=arr[pos].find(a);
    for(int i=index+1; i<arr[pos].index; ++i){
        int temp=arr[pos].arr[i];
        arr[temp].init_set(temp);
    }
    arr[pos].index = index+1;
}

void move_a_onto_b(int a,int b){
    if(a==b) return ;
    pos_a = find_block(a);
    pos_b = find_block(b);
    if(pos_a==pos_b)  return ;

    return_block(pos_a, a);
    return_block(pos_b, b);

    arr[pos_b].add(a);
    --arr[pos_a].index;
}

void move_a_over_b(int a,int b){
    if(a==b) return ;
    pos_a = find_block(a);
    pos_b = find_block(b);
    if(pos_a==pos_b)  return ; 
    
    return_block(pos_a, a);
    
    arr[pos_b].add(a);
    --arr[pos_a].index;
}

void pile_a_onto_b(int a,int b){
    if(a==b) return ;
    pos_a = find_block(a);
    pos_b = find_block(b);
    if(pos_a==pos_b)  return ; 

    return_block(pos_b,b);
    
    int index=arr[pos_a].find(a);
    for(int i=index; i<arr[pos_a].index; ++i){
        arr[pos_b].add(arr[pos_a].arr[i]);
    }
    arr[pos_a].index = index;
}

void pile_a_over_b(int a,int b){
    if(a==b) return ;
    pos_a = find_block(a);
    pos_b = find_block(b);
    if(pos_a==pos_b)  return ;
    
    int index = arr[pos_a].find(a);
    for(int i=index; i<arr[pos_a].index; ++i){
        arr[pos_b].add(arr[pos_a].arr[i]);
    }
    arr[pos_a].index = index;
}

void solve(){
    if(command1=="move" && command2=="onto"){
        move_a_onto_b(block_a,block_b);
    }
    else if(command1=="move" && command2=="over"){
        move_a_over_b(block_a,block_b);
    }
    else if(command1=="pile" && command2=="onto"){
        pile_a_onto_b(block_a,block_b);
    }
    else if(command1=="pile" && command2=="over"){
        pile_a_over_b(block_a,block_b);
    }
}
void init(int n){
    for(int i=0; i<n; ++i){
        arr[i].init_set(i);
    }
}
void output(){
    for(int i=0; i<n; ++i){
        printf("%d:",i);
        arr[i].output();
        printf("\n");
    }
}

int main()
{
    freopen("input.txt","r",stdin);
    scanf("%d",&n);
    init(n);
    while( cin >> command1 >> block_a >> command2 >> block_b){
        if(command1=="quit") break;
        solve();
    }
    output();
    return 0;
}

—— 生命的意义，在于赋予它意义。

原创http://blog.csdn.net/shuangde800，By D_Double