2393.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/* This Code is Submitted by wywcgs for Problem 2393 on 2006-10-19 at 21:37:14 */
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;

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

int map[N][N], vst[N][N], w, h;

int dis(int);
bool legal(int x, int y, int t) { return x >= 0 && x <= h && y >= 0 && y <= w && vst[x][y] != t; }

int main()
{
	int n;

	memset(vst, -1, sizeof(vst));
	memset(map, -1, sizeof(map));
	for(int t = 0; scanf("%d", &n) != EOF && n != 0; t++) {
		w = h = -1;
		for(int i = 0; i < n; i++) {
			int x, y; scanf("%d %d", &x, &y);
			map[x][y] = t; h >?= x; w >?= y;
		}
		printf("%d\n", dis(t));
	}
	
	return 0;
}

int dis(int t)
{
	int n;
	queue<int> Q;
	scanf("%d", &n);
	for(int i = 0; i < n; i++) {
		int x, y; scanf("%d %d", &x, &y);
		h >?= x; w >?= y; vst[x][y] = t;
		Q.push((x<<15)|y); Q.push(0);
	}
	while(!Q.empty()) {
		int p = Q.front(), x = p>>15, y = p&2047; Q.pop();
		int step = Q.front(); Q.pop();
		for(int i = 0; i < 4; i++) {
			int cx = x+DIR[i][0], cy = y+DIR[i][1];
			if(!legal(cx, cy, t)) continue;
			if(map[cx][cy] == t) return step+1;
			vst[cx][cy] = t; Q.push((cx<<15)|cy); Q.push(step+1);
		}
	}
	return -1;
}