POJ - 3346.cpp

#include <queue>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int SIZE = 110;
const int inf = 100000;
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};

struct Node {
	int x, y, s;
	Node() {}
	Node(int x, int y, int s) : x(x), y(y), s(s) {}
};

char map[SIZE][SIZE];
bool vis[SIZE][SIZE][30];
int dis[SIZE][SIZE][30];
int sx, sy, n, m;

inline bool isenter(int x, int y) {
	if (map[x][y] == '#' || isupper(map[x][y])) return true;
	return false;
}

void bfs(int sx, int sy) {
	queue<Node> q;
	while (!q.empty()) q.pop();
	for (int i = 0; i < n; ++ i) {
		for (int j = 0; j < m; ++ j) {
			fill(dis[i][j], dis[i][j] + 30, inf);
			fill(vis[i][j], vis[i][j] + 10, 0);
		}
	}
	q.push(Node(sx, sy, 0));
	vis[sx][sy][0] = 1; dis[sx][sy][0] = 0;
	while (!q.empty()) {
		Node now = q.front(); q.pop();
		vis[now.x][now.y][now.s] = false;
		for (int i = 0; i < 4; ++ i) {
			int xx = now.x + dx[i];
			int yy = now.y + dy[i];
			if (map[xx][yy] == '*') continue;
			if (isenter(xx, yy)) {
				dis[xx][yy][now.s] = min(dis[xx][yy][now.s], dis[now.x][now.y][now.s]);
				continue;
			}
			if (map[xx][yy] == '.') {
				if (dis[xx][yy][now.s] > dis[now.x][now.y][now.s]) {
					dis[xx][yy][now.s] = dis[now.x][now.y][now.s];
					if (!vis[xx][yy][now.s]) {
						vis[xx][yy][now.s] = true;
						q.push(Node(xx, yy, now.s));
					}
				}
			}
			if (isdigit(map[xx][yy])) {
				int cost = map[xx][yy] - '0';
				if (dis[xx][yy][now.s] > dis[now.x][now.y][now.s] + cost) {
					dis[xx][yy][now.s] = dis[now.x][now.y][now.s] + cost;
					if (!vis[xx][yy][now.s]) {
						vis[xx][yy][now.s] = true;
						q.push(Node(xx, yy, now.s));
					}
				}
				if (now.s < 26 && dis[xx][yy][now.s + 1] > dis[now.x][now.y][now.s]) {
					dis[xx][yy][now.s + 1] = dis[now.x][now.y][now.s];
					if (!vis[xx][yy][now.s + 1]) {
						vis[xx][yy][now.s + 1] = true;
						q.push(Node(xx, yy, now.s + 1));
					}
				}
			}
		}
	}
}

int main() {
	while (gets(map[0])) {
		if (strcmp(map[0], "--") == 0) break;
		n = 1; m = strlen(map[0]);
		do {
			gets(map[n]); 
			n ++;
		} while (strlen(map[n - 1]));
		for (int i = 0; i < n; ++ i) {
			for (int j = 0; j < m; ++ j) {
				if (map[i][j] == '$') {
					sx = i; sy = j;
				}
			}
		}
		bfs(sx, sy);
		int ret = inf;
		for (int i = 0; i < n; ++ i) {
			for (int j = 0; j < m; ++ j) {
				if (isenter(i, j)) {
					int d = (map[i][j] == '#') ? 0 : map[i][j] - 'A' + 1;
					for (int k = 0; k <= d; ++ k) 
						ret = min(ret, dis[i][j][k]);
				}
			}
		}
		if (ret == inf) puts("IMPOSSIBLE");
		else printf("%d\n", ret);
	}
	return 0;
}