b.cpp

ACM大赛基本练习题

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

#define COLOR 5
#define MAXN 25
#define MAXM 10
#define INF 100

typedef struct Ball Ball;
struct Ball
{
	int color;
	Ball *next;
};

const char color[COLOR] = { 'R', 'B', 'W', 'Y', 'G' };

Ball play[COLOR][MAXM];
Ball ball[MAXN];

int num[COLOR];
int n, m;
int minStep;

void ready()
{
	int i, j;
	for( i = 0; i < COLOR; ++i )
		for( j = 0; j < MAXM; ++j )
			play[i][j].color = i;
}

int find_color( char c )
{
	int i;

	for( i = 0; i < COLOR; ++i )
		if( color[i] == c )
			return i;

	return -1;
}

void read_it()
{
	int i;
	char st1[MAXN];
	char st2[MAXM];

	scanf( "%d %d", &n, &m );
	scanf( "%s", st1 );
	scanf( "%s", st2 );

	memset( num, 0, sizeof( num ) );
	
	for( i = 0; i < n; ++i )
	{
		ball[i].color = find_color( st1[i] );
		ball[i].next = &ball[i + 1];
	}
	ball[n - 1].next = NULL;

	for( i = 0; i < m; ++i )
		++num[ find_color( st2[i] ) ]; 

	minStep = INF;
}

void search_it( Ball *head, int nowStep )
{
	Ball *nowBall;
	Ball *tmp;
	Ball *last;

	int i;

	if( nowStep >= minStep )
		return;

	if( head == NULL )
	{
		minStep = nowStep;
		return;
	}

	for( nowBall = head; nowBall->next; nowBall = nowBall->next )
	{
		if( nowBall->color == nowBall->next->color 
			&& nowBall->next->next
			&& nowBall->next->next->color == nowBall->color )
		{
			last = nowBall->next->next->next;
			while( last && last->color == nowBall->color )
				last = last->next;

			if( nowBall == head )
				search_it( last, nowStep );
			else
			{
				tmp->next = last;
				search_it( head, nowStep );
				tmp->next = nowBall;
			}

			return;
		}

		tmp = nowBall;
	}

	for( i = 0; i < COLOR; ++i )
		if( num[i] > 0 )
		{
			--num[i];
			tmp = &play[i][ num[i] ];

			for( nowBall = head; nowBall; nowBall = nowBall->next )
				if( nowBall->color == tmp->color )
				{
					tmp->next = nowBall->next;
					nowBall->next = tmp;

					search_it( head, nowStep + 1 );
				
					nowBall->next = tmp->next;

					while( nowBall->next && nowBall->color == nowBall->next->color )
						nowBall = nowBall->next;
				}

			++num[i];
		}
}

void make_it()
{
	search_it( &ball[0], 0 );
	
	if( minStep == INF )
		printf( "lose\n" );
	else
		printf( "%d\n", minStep );
}

int main()
{
	int testCase, i;

	ready();

	scanf( "%d", &testCase );
	for( i = 0; i < testCase; ++i )
	{
		read_it();
		make_it();
	}

	return 0;
}