1020.cpp

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

/*  This Code is Submitted by wywcgs for Problem 1020 on 2006-02-06 at 22:41:21 */ 
#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;

const int MAX = 128;
const int INF = 1 << 30;

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

const Point DIR[] = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } };
const char ROAD_C[] = "|-|-";

class Edge {
public:
	int b, e, bd, ed, l;
};

char map[MAX][MAX];
int ins[MAX];

inline bool inter(char);
int green(int, int, int);

int main()
{
	int o[MAX][MAX], t, T, i, j, k;
	int w, h, time[MAX][4];
	Edge road[8*MAX];

	scanf("%d", &T);
	for(t = 0; t < T; t++) {
		scanf("%d %d\n", &h, &w);
		int in = 0, src, dis;
		for(i = 0; i < h; i++) {
			gets(map[i]);
			for(j = 1; j < w; j++)
				if(inter(map[i][j])) {
					o[i][j] = in; ins[in++] = (i << 8) + j;
					if(map[i][j] == 'S') src = o[i][j];
					else if(map[i][j] == 'D') dis = o[i][j];
				}
		}
		for(i = 0; i < in; i++)
			for(j = 0; j < 4; j++) time[i][j] = (i == src) ? 0 : INF;
		int en = 0;
		for(i = 0; i < in; i++) {
			int x = ins[i] >> 8, y = ins[i] & 127;
			for(j = 0; j < 4; j++) {
				int cx = x, cy = y;
				for(k = 0; true; k++) {
					cx += DIR[j].x; cy += DIR[j].y;
					if(inter(map[cx][cy])) {
						road[en].b = i; road[en].e = o[cx][cy]; road[en].bd = j; road[en].ed = (j+2)&3; road[en].l = k;
						en++; break;
					} else if(map[cx][cy] != ROAD_C[j]) break;
				}
			}
		}
		bool ex = true;
		while(ex) {
			ex = false;
			for(j = 0; j < en; j++) {
				if(time[road[j].b][road[j].bd]+road[j].l < time[road[j].e][road[j].ed]) {
					ex = true;
					time[road[j].e][road[j].ed] = time[road[j].b][road[j].bd] + road[j].l;
					int pass = green(road[j].e, road[j].ed, time[road[j].e][road[j].ed]);
					for(k = 0; k < 4; k++) time[road[j].e][k] = min(time[road[j].e][k], pass);
				}
			}
		}
		if(time[dis][0] == INF) printf("impossible\n");
		else printf("%d\n", time[dis][0]);
	}
	
	return 0;
}

inline bool inter(char m)
{
	return (m == 'S' || m == 'D' || m == '+' || isdigit(m));
}
int green(int b, int d, int t)
{
	int bd = 0, x = ins[b] >> 8, y = ins[b] & 127;
	if(map[x+1][y] != '|') bd = 2;
	if(!isdigit(map[x][y])) return t;
	else {
		bool have[4] = { false }; int inn = 0, i;
		for(i = 0; i < 4; i++) {
			int cx = x+DIR[i].x, cy = y+DIR[i].y;
			if(map[cx][cy] == ROAD_C[i]) inn++, have[i] = true;
		}
		int per = map[x][y] - '0', x = (t/per)%inn, nt = t - t%per;
		for(i = 0; i < x; i++)
			do bd = (bd+1)&3;
			while(!have[bd]);
		if(bd == d) return t;
		while(bd != d) {
			nt += per;
			do bd = (bd+1)&3;
			while(!have[bd]);
		}
		return nt;
	}
}