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
Submission Time | |
---|---|
Task | E - Magic Doors |
User | torimal |
Language | C (GCC 4.4.7) |
Score | 0 |
Code Size | 2292 Byte |
Status | CE |
Compile Error
./Main.c:1: fatal error: iostream: No such file or directory compilation terminated.