AOJ 2640: Prowler
これめっちゃ難しいと思うんですけど…
解法
自分の周りの 8 マスの状況を全部考えてみると, 次に移動できるマスが一意に決まりそうなことに気づきます。よって, 素直に最短経路を求めてその時に通ったマスの数を求めれば良いです。
自分は結構デバッグに時間がかかったのですが, 引っかかったのは,
.x.
.^x
..x
の時に, 2 行目にある x から 1 行目の x に手を入れ替えるのを忘れているところでした。
const ll INF = 1ll<<55; struct edge { int v; ll w; edge() {} edge(int v, ll w) : v(v), w(w) {}; }; vector<ll> dijkstra(int n, vector<vector<edge> >& G, int s) { vector<ll> d(n, LLONG_MAX/10); d[s] = 0; priority_queue<pair<ll, int> > que; que.push(make_pair(0ll, s)); while (!que.empty()) { auto p = que.top(); que.pop(); int u = p.second; ll dist = -p.first; if (dist > d[u]) continue; for (edge e : G[u]) { if (d[e.v] > d[u]+e.w) { d[e.v] = d[u] + e.w; que.push(make_pair(-d[e.v], e.v)); } } } return d; } int N, M; bool used[55][55]; inline int calcV(int y, int x, int dir, int hand) { return x + y*M + dir*N*M + hand*N*M*4; } // 今いる場所から壁を触れるのかを確かめる inline bool check(int y, int x, int dir, int hand, const vector<string>& board) { // 右手の向き int rdir = (2*dir+8-hand) % 8; int ny = y+dy8[rdir], nx = x+dx8[rdir]; if (ny < 0 || ny >= N || nx < 0 || nx >= M) return true; if (board[ny][nx] == '#') return true; return false; } int main() { cin.tie(0); ios::sync_with_stdio(false); cin >> N >> M; vector<string> board(N); for (int i = 0; i < N; i++) { cin >> board[i]; } int sy = -1, sx = -1, sdir = -1; int gy = -1, gx = -1; for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) { if (board[i][j] == '.' || board[i][j] == '#') continue; if (board[i][j] == 'G') { gy = i, gx = j; continue; } sy = i, sx = j; switch (board[i][j]) { case '>': sdir = 0; break; case '^': sdir = 1; break; case '<': sdir = 2; break; case 'v': sdir = 3; break; default: assert(0); break; } } // グラフを作る vector<vector<edge> > G(N*M*4*4); vector<vector<edge> > rG(N*M*4*4); for (int y = 0; y < N; y++) for (int x = 0; x < M; x++) { if (board[y][x] == '#') continue; for (int dir = 0; dir < 4; dir++) for (int hand = 0; hand < 4; hand++) { if (!check(y, x, dir, hand, board)) continue; int v = calcV(y, x, dir, hand); // 1 マス進む if (hand == 1 || hand == 2) { int ny = y+dy[dir], nx = x+dx[dir]; if (0 <= ny && ny < N && 0 <= nx && nx < M && board[ny][nx] != '#') { int nhand = hand+1; int u = calcV(ny, nx, dir, nhand); G[v].emplace_back(u, 100000); rG[u].emplace_back(v, 100000); } } // 右に変える if (hand >= 2) { int ndir = (dir+3)%4; int nhand = hand-2; int u = calcV(y, x, ndir, nhand); G[v].emplace_back(u, 1); rG[u].emplace_back(v, 1); } // 左に変える if (hand < 2) { int ndir = (dir+1)%4; int nhand = hand+2; int u = calcV(y, x, ndir, nhand); G[v].emplace_back(u, 1); rG[u].emplace_back(v, 1); } // 壁を変える for (int i = -1; i <= 1; i++) { int nhand = hand+i; if (nhand < 0 || nhand > 3) continue; if (!check(y, x, dir, nhand, board)) continue; int u = calcV(y, x, dir, nhand); G[v].emplace_back(u, 1); rG[u].emplace_back(v, 1); } if (hand==0) { int nhand = hand+2; if (!check(y, x, dir, nhand, board)) continue; int u = calcV(y, x, dir, nhand); G[v].emplace_back(u, 1); rG[u].emplace_back(v, 1); } if (hand==2) { int nhand = hand-2; if (!check(y, x, dir, nhand, board)) continue; int u = calcV(y, x, dir, nhand); G[v].emplace_back(u, 1); rG[u].emplace_back(v, 1); } } } auto d = dijkstra(4*4*N*M, G, calcV(sy, sx, sdir, 2)); ll dist = INF; int now = -1; for (int i = 0; i < 4; i++) for (int j = 0; j < 4; j++) { int v = calcV(gy, gx, i, j); if (dist > d[v]) { dist = d[v]; now = v; } } if (dist == INF) { cout << -1 << endl; return 0; } while (dist > 0) { used[(now/M)%N][now%M] = true; for (edge e : rG[now]) { if (d[e.v]+e.w == d[now]) { now = e.v; dist -= e.w; break; } } } used[sy][sx] = true; int ans = 0; for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) { if (used[i][j]) ans++; } cout << ans << endl; return 0; }
