2517.cpp

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

/* This Code is Submitted by wywcgs for Problem 2517 on 2007-07-02 at 16:32:56 */
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define CLEAR(a, b) memset(a, b, sizeof(a))

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

char map[N][N];
int n, m, vst[N][N][4];

bool legal(int x, int y) { return x >= 0 && x < n && y >= 0 && y < m && (map[x][y] == '+' || map[x][y] == 'X'); }

int main()
{
	int T;
	scanf("%d", &T);
	for(int t = 0; t < T; t++) {
		printf("Scenario #%d:\n", t+1);
		scanf("%d %d", &n, &m);
		FOR(i, 0, n) scanf("%s", map[i]);
		int bx, by;
		FOR(i, 0, n) FOR(j, 0, m)
			if(map[i][j] == 'U') { bx = i; by = j; }
		queue<int> Q; CLEAR(vst, -1);
		Q.push(bx); Q.push(by); Q.push(-1); Q.push(0);
		int bt, et; scanf("%d %d", &bt, &et); et += bt;
		int tm = -1;
		while(!Q.empty()) {
			int x = Q.front(); Q.pop();
			int y = Q.front(); Q.pop();
			int d = Q.front(); Q.pop();
			int s = Q.front(); Q.pop();
			if(s >= et) break;
			else if(s >= bt && map[x][y] == 'X') { tm = s; break; }
			FOR(i, 0, 4) {
				if((i+2)%4 == d) continue;
				int cx = x+DIR[i][0], cy = y+DIR[i][1];
				if(!legal(cx, cy)) continue;
				if(vst[cx][cy][i] == s+1) continue;
				vst[cx][cy][i] = s+1;
				Q.push(cx); Q.push(cy); Q.push(i); Q.push(s+1);
			}
		}
		if(tm == -1) printf("Impossible\n");
		else printf("%d\n", tm);
		printf("\n");
	}
	return 0;
}