[AtCoder] ABC 184 E – Third Avenue
問題
方針
文字列 'a’ のマスのリストを \( a \) とし、マス 'S’ からマス \( p \) の最短距離を \( d(p) \) とします。探索は迷路で使われるような幅優先探索を用います。現在いるマスがテレポート可能なマスの場合、そのマスのリストを探索し、最短距離が更新できるならばキューにそのマスを追加します。また、一度使用したテレポートのマスの文字は \( 1 \) 回で十分なので、その管理も行います。
コード
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int INF = 1000000000; int main() { int H, W; cin >> H >> W; string a[H]; vector<pair<int, int>> v[26]; deque<pair<int, int>> q; int d[H][W]; int gx, gy; for (int i = 0; i < H; i++) { cin >> a[i]; for (int j = 0; j < W; j++) { d[i][j] = INF; if ('a' <= a[i][j] && a[i][j] <= 'z') { v[a[i][j] - 'a'].push_back(make_pair(j, i)); } else if (a[i][j] == 'S') { q.push_back(make_pair(j, i)); d[i][j] = 0; } else if (a[i][j] == 'G') { gx = j; gy = i; } } } int dx[4] = {1, -1, 0, 0}; int dy[4] = {0, 0, 1, -1}; bool flag[26]{}; while (!q.empty()) { int x = q.front().first; int y = q.front().second; q.pop_front(); for (int i = 0; i < 4; i++) { int nx = x + dx[i]; int ny = y + dy[i]; if (nx < 0 || nx >= W || ny < 0 || ny >= H || a[ny][nx] == '#') continue; if (a[ny][nx] == 'G') { if (d[ny][nx] > d[y][x] + 1) { d[ny][nx] = d[y][x] + 1; break; } } else if (d[ny][nx] > d[y][x] + 1) { d[ny][nx] = d[y][x] + 1; q.push_back(make_pair(nx, ny)); } } if ('a' <= a[y][x] && a[y][x] <= 'z') { int id = a[y][x] - 'a'; if (flag[id]) continue; flag[id] = true; for (pair<int, int> p : v[id]) { if ( d[p.second][p.first] > d[y][x] + 1) { d[p.second][p.first] = d[y][x] + 1; q.push_back(p); } } } } if (d[gy][gx] == INF) { cout << "-1\n"; } else { cout << d[gy][gx] << "\n"; } return 0; }
ディスカッション
コメント一覧
まだ、コメントがありません