2298.cpp

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

/*  This Code is Submitted by wywcgs for Problem 2298 on 2006-08-03 at 00:17:22 */ 
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;

const int N = 6;
const int DIR[][2] = { { -1, 0 }, { 0, -1 }, { 1, 0 }, { 0, 1 } };

int wall[N][N], prev[N*N];

inline int hash(int x, int y) { return x*6+y; }
inline int legal(int x, int y) { return x >= 0 && x < N && y >= 0 && y < N; }

void bfs(int, int);
char dir(int, int);

int main()
{
	int bx, by, ex, ey, i, j;
	
	while(scanf("%d %d %d %d", &bx, &by, &ex, &ey) != EOF && bx != 0) {
		int b = hash(by-1, bx-1), e = hash(ey-1, ex-1);
		memset(wall, 0, sizeof(wall));
		for(i = 0; i < 3; i++) {
			int x1, x2, y1, y2; scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
			if(x1 == x2) {
				for(j = y1; j < y2; j++) {
					if(x1 != 6) wall[j][x1] |= 1 << 1;
					if(x1 != 0) wall[j][x1-1] |= 1 << 3;
				}
			} else {
				for(j = x1; j < x2; j++) {
					if(y1 != 6) wall[y1][j] |= 1;
					if(y1 != 0) wall[y1-1][j] |= 1 << 2;
				}
			}
		}
		bfs(b, e);
		int path[N*N], pn = 0;
		for(i = e; i != b; i = prev[i]) path[pn++] = i;
		path[pn++] = b;
		for(i = pn-2; i >= 0; i--) putchar(dir(path[i+1], path[i]));
		putchar('\n');
	}
	
	return 0;
}

void bfs(int b, int e)
{
	memset(prev, -1, sizeof(prev));
	queue<int> Q; Q.push(b); prev[b] = b;
	while(!Q.empty()) {
		int p = Q.front(); Q.pop();
		if(p == e) return;
		int px = p/6, py = p%6, i;
		for(i = 0; i < 4; i++) {
			int cx = px+DIR[i][0], cy = py+DIR[i][1], co = hash(cx, cy);
			if((wall[px][py]&(1<<i)) || !legal(cx, cy) || prev[co] != -1) continue;
			prev[co] = p; Q.push(co);
		}
	}
}
char dir(int b, int e)
{
	int by = b/6, bx = b%6, ey = e/6, ex = e%6;
	if(bx == ex)
		if(by > ey) return 'N';
		else return 'S';
	else
		if(bx > ex) return 'W';
		else return 'E';
}