2580.txt

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

Problem Id:2580  User Id:fzk 
Memory:68K  Time:0MS
Language:G++  Result:Accepted

Source 

#include "stdio.h"
#include "string.h"
#include "stdlib.h"

int k[20],keys[20][200],to[20][200];
int key[20];
int n,begin;

bool init()
{
	char w[100],num[100],t;
	int i,j,h;

	scanf( "%s", w );

	if( strcmp( "ENDOFINPUT", w ) == 0 )
		return false;

	scanf( "%d %d", &begin, &n );
	getchar();

	for( i=0; i<n; i++ )
	{
		k[i] = 0;
		while(1)
		{
			j=0;

			while(1)
			{
				t = getchar();
				if( t >= '0' && t <= '9' ) num[j++] = t;
				else break;
			}
			num[j] = '\0';
			
			to[i][ k[i] ] = atoi( num );
			keys[i][ k[i] ] = 0;

			while( t <= 'Z' && t >= 'A' )
			{
				keys[i][ k[i] ] |= 1 << (t-'A');
				t = getchar();
			}
			
			if(j)k[i]++;
			if( t == '\n' ) break;
		}
	}

	for( i=0; i<n; i++ )
	{
		key[i] = 0;
		do
		{
			t = getchar();
			if( t <= 'Z' && t >= 'A' )	key[i] |= 1 << (t-'A');
		}while( t != '\n' );
	}

	scanf( "%s", w );

	for( i=0; i<n; i++ )
	{
		for( j=0; j<k[i] && (h=to[i][j]) > i; j++ )
		{
			to[ h ][ k[h] ] = i;
			keys[ h ][ k[h] ] = keys[i][j];
			k[h]++;
		}
	}
	return true;
}

int KEY;
bool sign[20];

bool search( int s )
{
	int i;

	sign[s] = true;
	
	if( s == 0 ) return true;
	
	if( ( KEY | key[s] ) != KEY )
	{
		KEY |= key[s];
		return true;
	}

	for( i=0; i<k[s]; i++ )
	if( !sign[ to[s][i] ] && ( KEY | keys[s][i] ) == KEY )
	{
		if( search( to[s][i] ) ) return true;
	}

	return false;
}

void doit()
{
	int i;

	KEY = 0;
	while( 1 )
	{
		for( i=0; i<n; i++)
			sign[i] = false;

		if( !search( begin ) )
		{
			printf( "NO\n" );
			return;
		}
		
		if( sign[0] == true )
		{
			printf( "YES\n" );
			return;
		}
	}
}

int main()
{
	while(init())
		doit();

	return 0;
}