首页 > 资讯 > C++ > 正文

UVa 101 - The Blocks Problem

13-10-16 来源：[db:作者]

收藏我要投稿

题目：给你n个方块，有四种操作：

1.move a onto b，把a和b上面的方块都放回原来位置，然后把a放到b上面；

2.move a over b，把a上面的放回原处，然后把a放在b所在的方块堆的上面；

3.pile a onto b，把b上面的放回原来位置，然后把a所在的堆整体放到b上面；

4.pile a over b，吧a所在堆整体放到b所在堆的上面。

分析：模拟，数据结构。观察操作，如果是move就是先把a上面的还原，如果是onto就是先把b上面的还原。

然后，就是移动一堆到另一堆的上面（单个也认为是一堆）。所以设置两个基础操作：

1.将a上面的还原init_place(a)；

2.将a和上面的（可以没有上面的）放到b上面pile_a_to_b(a,b)。

那么上述的四组操作就变成下面了：

1.move a onto b，init_place(a)；init_place(b)；pile_a_to_b(a,b)；

2.move a over b，init_place(a)；pile_a_to_b(a,b)；

3.pile a onto b，init_place(b)；pile_a_to_b(a,b)；

4.pile a over b，pile_a_to_b(a,b)。

利用两个操作轻松解决。具体实现时设置一个place数组记录每个编号的方块对应的堆。

注意：如果a和b已经在一堆中就不要操作，此时认为不用移动，否则会WA。

#include <iostream>  
#include <cstdlib>  
#include <cstdio>   
  
using namespace std;  
  
int place[25];  
int stack[25][25];  
int top[25];  
  
//将a上面的放回原位   
void init_place( int a )  
{  
    int block,id = place[a];  
    while ( stack[id][top[id]] != a ) {  
        block = stack[id][top[id] --];  
        place[block] = block;  
        stack[block][++ top[block]] = block;  
    }  
}  
  
//将a和上面的全都移动到b上  
int  temp[25];  
void pile_a_to_b( int a, int b )  
{  
    int topt = -1,id = place[a],ID = place[b];  
    //先将a上面的逆序存入temp   
    while ( stack[id][top[id]] != a )  
        temp[++ topt] = stack[id][top[id] --];  
    //再存入a  
    place[a] = ID;  
    stack[ID][++ top[ID]] = a;  
    top[id] --;  
    //最后将temp里面的逆序存入b   
    while ( topt >= 0 ) {  
        place[temp[topt]] = ID;  
        stack[ID][++ top[ID]] = temp[topt --];  
    }  
}  
   
int main()  
{  
    int  n,a,b;  
    char oper[5],type[5];  
    while ( ~scanf("%d",&n) ) {  
        for ( int i = 0 ; i < n ; ++ i ) {  
            stack[i][0] = i;  
            place[i] = i;  
            top[i] = 0;  
        }  
        while ( scanf("%s",oper) && oper[0] != 'q' ) {  
            scanf("%d%s%d",&a,type,&b);  
              
            //如果ab在同一堆，不处理   
            if ( place[a] == place[b] )  
                continue;  
              
            //如果是move先把a上面的还原   
            if ( oper[0] == 'm' )  
                init_place( a );   
              
            //如果是onto先把b上面的还原   
            if ( type[1] == 'n' )  
                init_place( b );  
              
            //把A堆放在B堆上    
            pile_a_to_b( a, b );   
        }   
          
        for ( int i = 0 ; i < n ; ++ i ) {  
            printf("%d:",i);  
            int now = 0;  
            while ( now <= top[i] )  
                printf(" %d",stack[i][now ++]);  
            printf("\n");  
        }  
    }  
    return 0;  
}

点击复制链接与好友分享!回本站首页