1097.cpp

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

/*  This Code is Submitted by wywcgs for Problem 1097 on 2006-02-02 at 17:24:14 */ 
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;

const int MAX = 64;
const char *DIR_C = "nwse";
typedef pair<int, int> pii;

class Point {
public:
	int x, y;
};

const Point DIR[] = { { -1, 0 }, { 0, -1 }, { 1, 0 }, { 0, 1 } };

int w, h, rock[MAX][MAX];
bool vst[MAX][MAX][4];
queue<pii> Q;

int move();
inline void push(int, int, int, int);
inline bool legal(int, int);

int main()
{
	int i, j;

	while(scanf("%d %d", &h, &w) != EOF && h != 0) {
		memset(vst, false, sizeof(vst));
		for(i = 0; i < h; i++)
			for(j = 0; j < w; j++) scanf("%d", &rock[i][j]);
		printf("%d\n", move());
	}
	
	return 0;
}

int move()
{
	int bx, by, ex, ey, i; char dir[8];
	scanf("%d %d %d %d %s", &bx, &by, &ex, &ey, dir);
	for(i = 0; DIR_C[i] != dir[0]; i++) ;
	while(!Q.empty()) Q.pop();
	push(bx, by, i, 0);
	while(!Q.empty()) {
		pii t = Q.front(); Q.pop();
		int x = t.first >> 8, y = (t.first>>2) & 63, d = t.first & 3;
		if(x == ex && y == ey) return t.second;
		push(x, y, (d+1)&3, t.second+1); push(x, y, (d-1)&3, t.second+1);
		for(i = 0; i < 3; i++) {
			x += DIR[d].x; y += DIR[d].y;
			if(legal(x, y)) push(x, y, d, t.second+1);
			else break;
		}
	}
	return -1;
}
inline void push(int x, int y, int d, int step)
{
	if(!vst[x][y][d]) vst[x][y][d] = true, Q.push(pii((x<<8)|(y<<2)|d, step));
}
inline bool legal(int x, int y)
{
	return (x > 0 && x < h && y > 0 && y < w
				&& !rock[x-1][y-1] && !rock[x-1][y] && !rock[x][y-1] && !rock[x][y]);
}