Submission #101876
Source Code Expand
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <string>
#include <cctype>
#include <cstring>
using namespace std;
bool memo[30][30][1<<8];
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, -1, 0, 1};
class State
{
public:
int x,y,f,c;
State(int x, int y, int c, int f)
:x(x),y(y),c(c),f(f)
{}
bool operator<(const State& s) const {
return c > s.c;
}
};
int main()
{
int W, H;
memset(memo, 0, sizeof(memo));
cin >> H >> W;
vector<string> field(H);
for(int i=0; i<H; i++) {
cin >> field[i];
}
int sx, sy;
for(int i=0; i<H; i++)
for(int j=0; j<W; j++) {
if(field[i][j] == '^') {
sx = j;
sy = i;
}
}
priority_queue<State> q;
q.push(State(sx, sy, 0, 0));
int res = -1;
while(!q.empty()) {
State s = q.top(); q.pop();
if(memo[s.x][s.y][s.f]) continue;
memo[s.x][s.y][s.f] = 1;
if(field[s.y][s.x] == '$') {
res = s.c;
break;
}
for(int i=0; i<4; i++) {
int nx = s.x + dx[i];
int ny = s.y + dy[i];
int nc = s.c + 1 + __builtin_popcount(s.f);
int nf = s.f;
if(nx < 0 || ny < 0 || nx >= W || ny >= H) continue;
if(field[ny][nx] == '#') continue;
char c = field[ny][nx];
if(islower(c)) {
q.push(State(nx, ny, nc, nf));
q.push(State(nx, ny, nc + 1 + __builtin_popcount(s.f), nf | ( 1 << (c - 'a'))));
}
else if(isupper(field[ny][nx])) {
if((nf >> (c - 'A')) & 1) {
q.push(State(nx, ny, nc, nf));
q.push(State(nx, ny, nc, nf ^ (1 << (c - 'A'))));
}
}
else {
q.push(State(nx, ny, nc, nf));
}
}
}
cout << res << endl;
}
Submission Info
Submission Time |
|
Task |
E - Magic Doors |
User |
neteru_AA |
Language |
C++ (G++ 4.6.4) |
Score |
100 |
Code Size |
1679 Byte |
Status |
AC |
Exec Time |
58 ms |
Memory |
1568 KB |
Judge Result
Set Name |
All |
Score / Max Score |
100 / 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 |
21 ms |
936 KB |
10 |
AC |
23 ms |
996 KB |
11 |
AC |
58 ms |
1564 KB |
12 |
AC |
54 ms |
1060 KB |
13 |
AC |
22 ms |
928 KB |
14 |
AC |
22 ms |
1052 KB |
15 |
AC |
21 ms |
932 KB |
16 |
AC |
23 ms |
1184 KB |
17 |
AC |
24 ms |
1148 KB |
18 |
AC |
21 ms |
924 KB |
19 |
AC |
41 ms |
1568 KB |
2 |
AC |
20 ms |
1056 KB |
20 |
AC |
21 ms |
1060 KB |
3 |
AC |
20 ms |
928 KB |
4 |
AC |
20 ms |
932 KB |
5 |
AC |
21 ms |
1004 KB |
6 |
AC |
22 ms |
1060 KB |
7 |
AC |
21 ms |
936 KB |
8 |
AC |
22 ms |
1056 KB |
9 |
AC |
20 ms |
932 KB |