1723.cpp

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

/*  This Code is Submitted by wywcgs for Problem 1723 on 2006-01-29 at 01:36:09 */ 
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;

const int MAX = 200;
typedef pair<int, int> pii;

int wall[MAX][MAX][2], ex, ey;
queue<pii> Q;
bool vst[MAX][MAX];
int stack[MAX*MAX], top, r, u;

inline bool legal(int, int);
inline void push(int, int, int);
void DFPush(int, int, int);
int find(int, int);

int main()
{
	int n, m, i, j;

	while(scanf("%d %d", &n, &m) != EOF && n != -1) {
		memset(wall, 0, sizeof(wall)); memset(vst, false, sizeof(vst));
		r = u = 0;
		int x[2], dir, t;
		for(i = 0; i < n; i++) {
			scanf("%d %d %d %d", &x[1], &x[0], &dir, &t);
			for(j = 0; j < t; j++, x[1-dir]++) wall[x[0]][x[1]][dir] = 1, r = max(r, x[0]), u = max(u, x[1]);
		}
		for(i = 0; i < m; i++) {
			scanf("%d %d %d", &x[1], &x[0], &dir);
			wall[x[0]][x[1]][dir] = 2;
		}
		double cx, cy;
		scanf("%lf %lf", &cx, &cy);
		ex = (int)cy; ey = (int)cx; 
		ex = min(ex, MAX-1); ey = min(ey, MAX-1); r = max(r, ey); u = max(u, ex);
		printf("%d\n", find(0, 0));
	}
	
	return 0;
}

inline bool legal(int x, int y)
{
	return (x >= 0 && x <= u && y >= 0 && y <= r && !vst[x][y]);
}
inline void push(int x, int y, int step)
{
	Q.push(pii(x|(y<<8), step)); vst[x][y] = true; stack[top++] = x | (y << 8);
}
void DFPush(int x, int y, int step)
{
	top = 0; push(x, y, step);
	while(top-- != 0) {
		int cx = stack[top] & 255, cy = stack[top] >> 8;
		if(legal(cx-1, cy) && wall[cx][cy][0] == 0) push(cx-1, cy, step);
		if(legal(cx+1, cy) && wall[cx+1][cy][0] == 0) push(cx+1, cy, step);
		if(legal(cx, cy-1) && wall[cx][cy][1] == 0) push(cx, cy-1, step);
		if(legal(cx, cy+1) && wall[cx][cy+1][1] == 0) push(cx, cy+1, step);
	}
}
int find(int x, int y)
{
	while(!Q.empty()) Q.pop();
	DFPush(x, y, 0);
	while(!Q.empty()) {
		pii t = Q.front(); Q.pop();
		int cx = t.first & 255, cy = t.first >> 8;
		if(cx == ex && cy == ey) return t.second;
		else {
			if(legal(cx-1, cy) && wall[cx][cy][0] == 2) DFPush(cx-1, cy, t.second+1);
			if(legal(cx+1, cy) && wall[cx+1][cy][0] == 2) DFPush(cx+1, cy, t.second+1);
			if(legal(cx, cy-1) && wall[cx][cy][1] == 2) DFPush(cx, cy-1, t.second+1);
			if(legal(cx, cy+1) && wall[cx][cy+1][1] == 2) DFPush(cx, cy+1, t.second+1);
		}
	}
	
	return -1;
}