Poj Solution 2580

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

#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] = '';
            
            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( "NOn" );
            return;
        }
        
        if( sign[0] == true )
        {
            printf( "YESn" );
            return;
        }
    }
}

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

    return 0;
}