2187.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 2187 on 2006-03-27 at 15:36:19 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX = 128;
const int DIR[][2] = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } };

int w, h;
char maze[MAX][MAX];

inline bool legal(int x, int y) { return (x >= 0 && x < h && y >= 0 && y < w); }
bool go(int, int);

int main()
{
	int enter[MAX*MAX], i, j;
	
	while(scanf("%d %d\n", &w, &h) != EOF && w != 0) {
		memset(maze, 'X', sizeof(maze));
		int en = 0, goal;
		for(i = 0; i < h; i++) {
			for(j = 0; j < w; j++) {
				char ch = getchar();
				if(ch == '\n') { ungetc('\n', stdin); break; }
				else maze[i][j] = ch;
				if(ch == 'E') enter[en++] = (i << 7) | j;
				else if (ch == 'G') goal = (i << 7) | j;
			}
			while(getchar() != '\n');
		}
		int gx = goal >> 7, gy = goal & 127;
		for(i = 0; i < 4; i++) {
			for(j = 0; true; j++) {
				int cx = gx + j*DIR[i][0], cy = gy + j*DIR[i][1];
				if(!legal(cx, cy) || maze[cx][cy] == 'X') break;
				maze[cx][cy] = 'G';
			}
		}
		int good = 0;
		for(i = 0; i < en; i++)
			if(go(enter[i]>>7, enter[i]&127)) good++;
		printf("The goal would be found from %d out of %d entrances.\n", good, en);
	}
	
	return 0;
}

bool go(int x, int y)
{
	int o;
	if(x == h-1) o = 0;
	else if(y == 0) o = 1;
	else if(x == 0) o = 2;
	else o = 3;
	while(true) {
		if(maze[x][y] == 'G') return true;
		int cx = x+DIR[o][0], cy = y+DIR[o][1];
		if(!legal(cx, cy)) return false;
		else if(maze[cx][cy] == 'X') o = (o-1)&3;
		else {
			int wx = cx+DIR[(o+1)&3][0], wy = cy+DIR[(o+1)&3][1];
			if(maze[wx][wy] != 'X') { cx = wx; cy = wy; o = (o+1)&3; }
			x = cx; y = cy;
		}
	}
}