Poj Solution 2816

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

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


char map[200][200];
bool ok[200][200];

int gx, gy, n, m, t, r;
const int dx[] = { -1, 0, 1, 0 };
const int dy[] = {  0, 1, 0, -1 };

void flag_ok( ) {
    int i, j;
    for( i=gx, j=gy; map[i][j] != 'X'; i++ )
        ok[i][j] = true;
    for( i=gx, j=gy; map[i][j] != 'X'; i-- )
        ok[i][j] = true;
    
    for( i=gx, j=gy; map[i][j] != 'X'; j++ )
        ok[i][j] = true;
    for( i=gx, j=gy; map[i][j] != 'X'; j-- )
        ok[i][j] = true;
}

bool go( int x, int y ) {
    bool key = true;
    int i;
    
    for( i=0; i<4; i++ )
    if( map[x+dx[i]][y+dy[i]] != 'X' )
        t = i;
    
    r = (t+1)%4;
    
    while( 1 ) 
    {
        if( ok[x][y] )
            return true;
        if( !key && map[x][y] == 'E' )
            return false;

        if( map[x+dx[r]][y+dy[r]] != 'X' ) {
            t = r;
            r = (t+1)%4;
        }

        for( i=0; i<4; i++ )
            if( map[x+dx[t]][y+dy[t]] == 'X' ) {
                t = (t+3)%4;
                r = (t+1)%4;
            }
            else
                break;

        if( i < 4 ) {
            x += dx[t];
            y += dy[t];
        }
        else
            return false;
        key = false;
    }
    return false;        
}

int main( ) {
    int n, m, i, j, a, b;
    char c;
    
    while( 1 ) {
        scanf( "%d%d", &m, &n );
        if( n < 3 && m < 3 )
            break;
        memset( map, 'X', sizeof map );
        memset( ok, 0, sizeof ok );
        
        getchar( );
        getchar( );
        for( i=0; i<n; i++ ) {
            for( j=1; ;j++ ) {
                c=getchar( );
                if( c == 'n' )
                    break;
                if( c == 'G' )
                    gx = i, gy = j;
                map[i][j] = c;
            }
        }
        
        flag_ok( );
        a = b = 0;
        for( i=0; i<n; i++ )
        for( j=1; j<=m; j++ )
        if( map[i][j] == 'E' )
        {
            b++;
            if( go( i, j ) )
                a++;
        }
        
        printf( "The goal would be found from %d out of %d entrances.n", a, b );
    }
    return 0;
}
											
This entry was posted in poj. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *