Submission #106574

---

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

Compile Error

./Main.c:1: fatal error: iostream: No such file or directory
compilation terminated.