Submission #486929
Source Code Expand
/*
* e.cc: E:
*/
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
using namespace std;
/* constant */
const int MAX_H = 30;
const int MAX_W = 30;
const int DN = 8;
const int DBITS = 1 << DN;
const int DMASK = DBITS - 1;
const int INF = 1 << 30;
const int dxs[] = {1, 0, -1, 0}, dys[] = {0, -1, 0, 1};
/* typedef */
struct Stat {
int x, y, bits, d;
Stat() {}
Stat(int _x, int _y, int _bits, int _d): x(_x), y(_y), bits(_bits), d(_d) {}
};
/* global variables */
int flds[MAX_H][MAX_W];
int dists[MAX_H][MAX_W][DBITS];
Stat prvs[MAX_H][MAX_W][DBITS];
int pds[DN];
/* subroutines */
/* main */
int main() {
int h, w;
cin >> h >> w;
memset(flds, 0, sizeof(flds));
int sx, sy, gx, gy;
for (int y = 0; y < h; y++) {
string line;
cin >> line;
for (int x = 0; x < w; x++) {
if (line[x] == '#')
flds[y][x] = -1;
else if (line[x] == '^')
sx = x, sy = y;
else if (line[x] == '$')
gx = x, gy = y;
else if (line[x] >= 'a' && line[x] <= 'h')
flds[y][x] = line[x] - 'a' + 1;
else if (line[x] >= 'A' && line[x] <= 'H')
flds[y][x] = line[x] - 'A' + 1 + DN;
}
}
for (int y = 0; y < h; y++)
for (int x = 0; x < w; x++)
for (int bits = 0; bits < DBITS; bits++)
dists[y][x][bits] = INF;
dists[sy][sx][0] = 0;
prvs[sy][sx][0] = Stat(sx, sy, 0, -1);
queue<Stat> q;
q.push(Stat(sx, sy, 0, 0));
int gbits = -1;
while (! q.empty()) {
Stat u = q.front(); q.pop();
if (dists[u.y][u.x][u.bits] != u.d) continue;
if (u.x == gx && u.y == gy) {
gbits = u.bits;
break;
}
int vd = u.d + 1;
for (int di = 0; di < 4; di++) {
int vx = u.x + dxs[di], vy = u.y + dys[di];
if (vx >= 0 && vx < w && vy >= 0 && vy < h && flds[vy][vx] >= 0) {
int vbits = u.bits, vf = flds[vy][vx];
if (vf >= 1 && vf <= DN)
vbits |= 1 << (vf - 1);
else if (vf > DN && ! (vbits & (1 << (vf - DN - 1)))) continue;
if (dists[vy][vx][vbits] > vd) {
dists[vy][vx][vbits] = vd;
q.push(Stat(vx, vy, vbits, vd));
prvs[vy][vx][vbits] = u;
}
}
}
}
if (dists[gy][gx][gbits] >= INF) {
cout << -1 << endl;
return 0;
}
int mt = 0;
memset(pds, 0, sizeof(pds));
for (int y = gy, x = gx, bits = gbits; prvs[y][x][bits].d > 0;) {
Stat u = prvs[y][x][bits];
int uf = flds[u.y][u.x];
if (uf >= 1 && uf <= DN) {
int k = uf - 1;
if (pds[k] > 0) {
mt += pds[k] - u.d;
for (int i = 0; i < DN; i++)
if (pds[i]) mt++;
pds[k] = 0;
}
}
else if (uf > DN) {
int k = uf - DN - 1;
if (pds[k] == 0) pds[k] = u.d;
}
x = u.x, y = u.y, bits = u.bits;
}
cout << (dists[gy][gx][gbits] + mt) << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
E - Magic Doors |
User |
tnakao |
Language |
C++ (GCC 4.4.7) |
Score |
0 |
Code Size |
3127 Byte |
Status |
WA |
Exec Time |
44 ms |
Memory |
5544 KB |
Judge Result
Set Name |
All |
Score / Max Score |
0 / 100 |
Status |
|
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 |
33 ms |
1048 KB |
10 |
WA |
30 ms |
1172 KB |
11 |
AC |
44 ms |
5544 KB |
12 |
AC |
36 ms |
4012 KB |
13 |
AC |
33 ms |
1324 KB |
14 |
AC |
32 ms |
1484 KB |
15 |
AC |
32 ms |
1356 KB |
16 |
AC |
35 ms |
3092 KB |
17 |
WA |
35 ms |
2632 KB |
18 |
WA |
37 ms |
4496 KB |
19 |
WA |
37 ms |
5264 KB |
2 |
AC |
30 ms |
1116 KB |
20 |
WA |
30 ms |
2000 KB |
3 |
AC |
29 ms |
984 KB |
4 |
AC |
29 ms |
1104 KB |
5 |
WA |
29 ms |
1100 KB |
6 |
AC |
29 ms |
1100 KB |
7 |
WA |
29 ms |
1096 KB |
8 |
AC |
29 ms |
1100 KB |
9 |
AC |
30 ms |
1160 KB |