Submission #487222
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) {}
bool operator>(const Stat& s) const { return d > s.d; }
void print() {printf("Stat: x=%d, y=%d, bits=%02x, d=%d\n", x, y, bits, d);}
};
/* global variables */
int flds[MAX_H][MAX_W];
int dists[MAX_H][MAX_W][DBITS], ds0[MAX_H][MAX_W][DBITS];
Stat prvs[MAX_H][MAX_W][DBITS];
int bnums[DBITS];
/* subroutines */
/* main */
int main() {
for (int bits = 0; bits < DBITS; bits++) {
bnums[bits] = 0;
for (int i = 0; i < DN; i++)
if (bits & (1 << i)) bnums[bits]++;
}
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] = ds0[y][x][bits] = INF;
dists[gy][gx][0] = ds0[gy][gx][0] = 0;
prvs[gy][gx][0] = Stat(gx, gy, 0, -1);
priority_queue<Stat,vector<Stat>,greater<Stat> > q;
q.push(Stat(gx, gy, 0, 0));
while (! q.empty()) {
Stat u = q.top(); q.pop();
if (dists[u.y][u.x][u.bits] != u.d) continue;
//u.print();
if (u.x == sx && u.y == sy && u.bits == 0) break;
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];
int vd = u.d + 1, vd0 = ds0[u.y][u.x][u.bits] + 1;
if (vf > DN) {
int k = vf - DN - 1, bk = 1 << k;
vbits |= bk;
}
else if (vf >= 1) {
int k = vf - 1, bk = 1 << k;
if (vbits & bk) {
Stat pu = u;
while (prvs[pu.y][pu.x][pu.bits].bits & bk)
pu = prvs[pu.y][pu.x][pu.bits];
vd += vd0 - ds0[pu.y][pu.x][pu.bits] + bnums[vbits];
vbits &= ~bk;
}
}
if (dists[vy][vx][vbits] > vd) {
dists[vy][vx][vbits] = vd;
ds0[vy][vx][vbits] = vd0;
q.push(Stat(vx, vy, vbits, vd));
prvs[vy][vx][vbits] = u;
}
}
}
}
cout << (dists[sy][sx][0] >= INF ? -1 : dists[sy][sx][0]) << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
E - Magic Doors |
User |
tnakao |
Language |
C++ (GCC 4.4.7) |
Score |
0 |
Code Size |
3205 Byte |
Status |
WA |
Exec Time |
89 ms |
Memory |
6312 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 |
25 ms |
808 KB |
10 |
WA |
25 ms |
1056 KB |
11 |
AC |
89 ms |
6312 KB |
12 |
AC |
48 ms |
4640 KB |
13 |
AC |
24 ms |
1060 KB |
14 |
AC |
25 ms |
1316 KB |
15 |
AC |
25 ms |
1320 KB |
16 |
AC |
34 ms |
3296 KB |
17 |
WA |
37 ms |
3244 KB |
18 |
WA |
32 ms |
5088 KB |
19 |
WA |
61 ms |
6180 KB |
2 |
AC |
24 ms |
804 KB |
20 |
WA |
29 ms |
2088 KB |
3 |
AC |
24 ms |
932 KB |
4 |
AC |
26 ms |
932 KB |
5 |
AC |
25 ms |
928 KB |
6 |
AC |
24 ms |
804 KB |
7 |
WA |
26 ms |
916 KB |
8 |
AC |
25 ms |
924 KB |
9 |
AC |
24 ms |
932 KB |