1208.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include <stdio.h>
#include <string.h>


typedef int block;
typedef int* block_pos;
block blocks[25][30];

const int none=-1;
int n;

bool init()
{
	int i,j;
	
	if( scanf("%d",&n)!=1 )return false;
	
	for( i=0; i<n; i++ )
	{
		blocks[i][0] = i;

		for( j=1; j<=n ;j++ )
			blocks[i][j] = none;
	}

	return true;
}

//base operations

block_pos find(block a)
{
	int i,j;
	for( i=0; i<n; i++ )
	for( j=0; blocks[i][j] != none ; j++ )
	{
		if( blocks[i][j] == a )	return &blocks[i][j];
	}
}

block_pos top(block_pos p)
{
	for( ; *p!=none ; p++)
		;

	return p;
}

block_pos bottom(block_pos p)
{
	for( ; ( p-(block_pos)blocks ) % sizeof(blocks[0]) ; p--)
		;
	return p;
}


void move(block_pos p1,block_pos p2)
{
	*p2=*p1;
	*p1=none;
}

void return_above(block_pos p)
{
	block_pos q;

	for( p++ ; *p!=none ; p++ )
	{
		q = top( blocks[*p] );
		*q = *p;
		*p = none;
	}	
}

//operations

void move_onto(block a,block b)
{
	block_pos p1=find(a), p2=find(b);
	
	return_above( p1 );
	return_above( p2 );
	
	p2 = top( p2 );
	move( p1, p2 );
}

void move_over(block a,block b)
{
	block_pos p1=find(a), p2=find(b);

	return_above( p1 );

	p2 = top( p2 );
	move( p1, p2 );
}

void pile_onto(block a,block b)
{
	block_pos p1=find(a), p2=find(b);
	
	return_above( p2 );
	
	for( p2=top( p2 ); *p1!=none ; p1++,p2++ )
		move( p1,p2 );
}

void pile_over(block a,block b)
{
	block_pos p1=find(a), p2=find(b);

	for( p2=top( p2 ); *p1!=none; p1++,p2++ )
		move( p1,p2 );

}

//print blocks

void print()
{
	int i,j;
	for( i=0; i<n; i++ )
	{
		printf( "%d:", i );
		for( j=0; blocks[i][j]!=none; j++ )
			printf( " %d", blocks[i][j] );
		
		printf("\n");
	}
	return ;
}



void doit()
{
	char word1[10],word2[10];
	int a, b;

	while(1)
	{
		scanf("%s",word1);

		if( strcmp(word1,"quit") == 0 ) break;

		scanf("%d %s %d", &a, word2, &b);
		
		if( a == b || top( find(a) ) == top( find(b) ) )
			continue;

		if( strcmp(word1,"move") == 0 )
		{
			if( strcmp(word2,"onto") == 0 )
			{
				move_onto( a, b );
			}
			else
			{
				move_over( a, b );
			}
		}
		else
		{
			if( strcmp(word2,"onto") == 0 )
			{
				pile_onto( a, b );
			}
			else
			{
				pile_over( a, b );
			}
		}

	}
	
	return ;
}
	


		
int main()
{
	while(init())
	{
		doit();
		print();
	}	
	return 0;
}