Submission #106575
Source Code Expand
#include <iostream>
#include <cctype>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
using namespace std;
#define FOR(i, a, n) for(int i = (a); i < (n); i++)
#define REP(i, n) FOR(i, 0, n)
#define RFOR(i, a, n) for(int i = (n) - 1; i >= (a); i--)
#define RREP(i, n) RFOR(i, 0, n)
#define ALL(v) (v).begin(), (v).end()
#define SIZE(v) (int)(v).size()
#define fst first
#define snd second
typedef long long ll;
typedef pair<int, int> pii;
const int MAX_L = 35;
const int MAX_S = 1 << 8;
const int MAX_V = MAX_L * MAX_L * MAX_S;
const int dx[] = {0, 1, 0, -1}, dy[] = {-1, 0, 1, 0};
const int N = 8;
const int INF = 1 << 28;
struct Edge{
int to, cost;
};
int w, h, n, V;
pii s, t;
int circles[26];
int doors[26];
char a[MAX_L][MAX_L];
vector<Edge> g[MAX_V];
int d[MAX_V];
inline int ix(int S, int i, int j){
return S * h * w + i * w + j;
}
inline bool is_door(char c){
return 'A' <= c && c <= 'H';
}
inline bool is_circle(char c){
return 'a' <= c && c <= 'h';
}
int solve(){
REP(S, 1 << N) REP(i, h) REP(j, w){
REP(T, 1 << N) if(!(~S & T)){
int cost = __builtin_popcount(T) + 1;
REP(k, 4){
int ni = i + dy[k], nj = j + dx[k];
if(0 <= ni && ni < h && 0 <= nj && nj < w
&& a[ni][nj] != '#'
&& (!is_door(a[ni][nj]) || (1 << (a[ni][nj] - 'A')) & T)){
g[ix(S, i, j)].push_back((Edge){ix(T, ni, nj), cost});
}
}
if(is_circle(a[i][j])){
g[ix(S, i, j)].push_back((Edge){ix(T | (1 << a[i][j] - 'a'), i, j), cost});
}
}
}
fill(d, d + MAX_V, INF);
priority_queue< pii, vector<pii>, greater<pii> > pq;
d[ix(0, s.fst, s.snd)] = 0;
pq.push(pii(0, ix(0, s.fst, s.snd)));
while(!pq.empty()){
pii p = pq.top(); pq.pop();
int v = p.snd;
if(p.fst > d[v]) continue;
REP(i, SIZE(g[v])){
Edge &e = g[v][i];
if(d[e.to] > d[v] + e.cost){
d[e.to] = d[v] + e.cost;
pq.push(pii(d[e.to], e.to));
}
}
}
int r = INF;
REP(S, 1 << N) r = min(r, d[ix(S, t.fst, t.snd)]);
return (r == INF ? -1 : r);
}
int main(){
cin >> h >> w;
REP(i, h) REP(j, w){
cin >> a[i][j];
if(a[i][j] == '^') s = pii(i, j);
if(a[i][j] == '$') t = pii(i, j);
}
cout << solve() << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
E - Magic Doors |
User |
torimal |
Language |
C++ (GCC 4.4.7) |
Score |
0 |
Code Size |
2292 Byte |
Status |
MLE |
Exec Time |
1349 ms |
Memory |
211200 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 |
53 ms |
9636 KB |
10 |
AC |
62 ms |
12188 KB |
11 |
MLE |
1349 ms |
211200 KB |
12 |
MLE |
910 ms |
107264 KB |
13 |
AC |
147 ms |
23212 KB |
14 |
AC |
159 ms |
25256 KB |
15 |
AC |
150 ms |
23720 KB |
16 |
AC |
546 ms |
73468 KB |
17 |
AC |
539 ms |
69032 KB |
18 |
MLE |
1113 ms |
149656 KB |
19 |
MLE |
1189 ms |
144428 KB |
2 |
AC |
41 ms |
9760 KB |
20 |
AC |
327 ms |
46084 KB |
3 |
AC |
41 ms |
9820 KB |
4 |
AC |
45 ms |
10240 KB |
5 |
AC |
49 ms |
10624 KB |
6 |
AC |
49 ms |
10920 KB |
7 |
AC |
61 ms |
12316 KB |
8 |
AC |
67 ms |
12292 KB |
9 |
AC |
46 ms |
10524 KB |