Submission #106577
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(){
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;
int S = v / (h * w), i = v % (h * w) / w, j = v % w;
if(p.fst > d[ix(S, i, j)]) continue;
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)){
int to = ix(T, ni, nj);
if(d[to] > d[v] + cost){
d[to] = d[v] + cost;
pq.push(pii(d[to], to));
}
}
}
if(is_circle(a[i][j])){
int to = ix(T | (1 << a[i][j] - 'a'), i, j);
if(d[to] > d[v] + cost){
d[to] = d[v] + cost;
pq.push(pii(d[to], 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 |
100 |
Code Size |
2283 Byte |
Status |
AC |
Exec Time |
318 ms |
Memory |
9508 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 |
37 ms |
9336 KB |
10 |
AC |
41 ms |
9380 KB |
11 |
AC |
100 ms |
9380 KB |
12 |
AC |
235 ms |
9344 KB |
13 |
AC |
38 ms |
9332 KB |
14 |
AC |
38 ms |
9384 KB |
15 |
AC |
38 ms |
9376 KB |
16 |
AC |
165 ms |
9504 KB |
17 |
AC |
163 ms |
9452 KB |
18 |
AC |
39 ms |
9376 KB |
19 |
AC |
318 ms |
9508 KB |
2 |
AC |
37 ms |
9380 KB |
20 |
AC |
43 ms |
9388 KB |
3 |
AC |
38 ms |
9372 KB |
4 |
AC |
38 ms |
9340 KB |
5 |
AC |
38 ms |
9388 KB |
6 |
AC |
37 ms |
9376 KB |
7 |
AC |
38 ms |
9372 KB |
8 |
AC |
43 ms |
9372 KB |
9 |
AC |
38 ms |
9380 KB |