2816.txt

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

Problem Id:2816  User Id:fzk 
Memory:104K  Time:0MS
Language:C++  Result:Accepted

Source 

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