# Poj Solution 2580

```http://poj.org/problem?id=2580

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

int k,keys,to;
int key;
int n,begin;

bool init()
{
char w,num,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] = '';

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;

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( "NOn" );
return;
}

if( sign == true )
{
printf( "YESn" );
return;
}
}
}

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

return 0;
}
```
This entry was posted in poj. Bookmark the permalink.