2504.cpp

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

/* This Code is Submitted by wywcgs for Problem 2504 on 2007-06-05 at 10:14:38 */
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#include <cctype>
using namespace std;

const int N = 128, P = 32;
const int DIR[][2] = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };

bool vst[N][N][P];
char map[N][N];

class Data {
public:
	int x, y, num, t;
	Data(int cx, int cy, int cn, int ct) : x(cx), y(cy), num(cn), t(ct) {}
	bool operator >(const Data& d) const { return t > d.t; }
};

void update(priority_queue< Data, vector<Data>, greater<Data> >&, int, int);

int main()
{
	int n, m;
	while(true) {
		scanf("\n");
		for(n = 0; true; n++) {
			gets(map[n]);
			if(map[n][0] == '-') return 0;
			else if(map[n][0] == 0) break;
		}
		m = strlen(map[0]);
		memset(vst, false, sizeof(vst));
		priority_queue< Data, vector<Data>, greater<Data> > Q;
		for(int i = 0; i < n; i++)
			{ update(Q, i, 0); update(Q, i, m-1); }
		for(int i = 0; i < m; i++)
			{ update(Q, 0, i); update(Q, n-1, i); }
		int res = -1;
		while(!Q.empty()) {
			Data d = Q.top(); Q.pop();
			int x = d.x, y = d.y, num = d.num, s = d.t;
			if(vst[x][y][num]) continue;
			vst[x][y][num] = true;
			for(int i = 0; i < 4; i++) {
				int cx = x+DIR[i][0], cy = y+DIR[i][1];
				if(cx < 0 || cx >= n || cy < 0 || cy >= m) continue;
				if(map[cx][cy] == '*' || map[cx][cy] == '#' || isupper(map[cx][cy])) continue;
				if(map[cx][cy] == '$') { res = s; break; }
				if(isdigit(map[cx][cy])) {
					if(!vst[cx][cy][num])
						Q.push(Data(cx, cy, num, s+map[cx][cy]-'0'));
					if(num != 0 && !vst[cx][cy][num-1])
						Q.push(Data(cx, cy, num-1, s));
				}
				if(map[cx][cy] == '.' && !vst[cx][cy][num])
					Q.push(Data(cx, cy, num, s));
			}
			if(res != -1) break;
		}
		if(res < 0) printf("IMPOSSIBLE\n");
		else printf("%d\n", res);
	}
	return 0;
}

void update(priority_queue< Data, vector<Data>, greater<Data> >& Q, int x, int y)
{
	int num = 0;
	if(map[x][y] == '*') return;
	if(isupper(map[x][y])) num = map[x][y]-'A'+1;
	Q.push(Data(x, y, num, 0));
}