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;
}