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
AC × 16
MLE × 4
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