Submission #102341


Source Code Expand

#include <iostream>
#include <queue>
#include <set>
#include <cctype>
using namespace std;

#define rep(i, n) for(int i=0; i<int(n); i++)
#define mp make_pair
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};

int main() {
	int H, W;
	cin >> H >> W;
	char A[H][W];
	rep(i, H) rep(j, W) cin >> A[i][j];

	priority_queue<pair<int, int> > Q;
	rep(i, H) rep(j, W) if (A[i][j] == '^')
		Q.push(mp(0, i*W + j));
	set<int> M;
	while(!Q.empty()) {
		int d = -Q.top().first;
		int v = Q.top().second;
		Q.pop();
		if (M.count(v)) continue;
		M.insert(v);
		int ci = (v&1023)/W;
		int cj = (v&1023)%W;
		if (A[ci][cj] == '$') {
			cout << d << endl;
			return 0;
		}
		int mask = v>>10;
		int cnt = __builtin_popcount(mask);
		rep(k, 4) {
			int ai = ci+dy[k], aj = cj+dx[k];
			if (min(ai, aj) < 0 || H <= ai || W <= aj || A[ai][aj] == '#') continue;
			if (isupper(A[ai][aj]) && !(mask>>(A[ai][aj]-'A')&1)) continue;
			Q.push(mp(-(d + cnt + 1), mask<<10 | (ai*W+aj)));
		}
		if (islower(A[ci][cj])) Q.push(mp(-(d + cnt + 1), (mask | 1<<(A[ci][cj]-'a')) << 10 | (ci*W + cj)));
		rep(k, 8) if (mask>>k&1) Q.push(mp(-d, (mask & ~(1<<k)) << 10 | (ci*W + cj)));
	}
	cout << -1 << endl;
}

Submission Info

Submission Time
Task E - Magic Doors
User negainoido
Language C++ (GCC 4.4.7)
Score 100
Code Size 1236 Byte
Status AC
Exec Time 308 ms
Memory 6168 KB

Judge Result

Set Name All
Score / Max Score 100 / 100
Status
AC × 20
Set Name Test Cases
All 1, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 2, 20, 3, 4, 5, 6, 7, 8, 9
Case Name Status Exec Time Memory
1 AC 20 ms 804 KB
10 AC 23 ms 936 KB
11 AC 165 ms 3496 KB
12 AC 308 ms 6168 KB
13 AC 20 ms 800 KB
14 AC 21 ms 804 KB
15 AC 21 ms 752 KB
16 AC 25 ms 932 KB
17 AC 32 ms 1060 KB
18 AC 23 ms 812 KB
19 AC 108 ms 2980 KB
2 AC 20 ms 844 KB
20 AC 27 ms 940 KB
3 AC 21 ms 804 KB
4 AC 20 ms 928 KB
5 AC 21 ms 936 KB
6 AC 21 ms 808 KB
7 AC 22 ms 804 KB
8 AC 28 ms 940 KB
9 AC 21 ms 808 KB