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
AC × 20
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