Approach
Breadth-first search
For ABC405 D — Escape Route, the implementation explores reachable states in layers, which is the standard shape for unweighted shortest paths and minimum-step transitions.
- Model each valid configuration as a state and each legal move as an edge.
- Seed the queue with the starting state and mark it immediately.
- Expand each state once, recording distance or reachability for unseen neighbours.
Code notes
- 68 lines of C++ from the credited upstream file abc405_d.cpp.
- The implementation visibly relies on sequence storage, work queue.
- 8 loop blocks detected.
Complexity
Verify that each state and transition is processed only a bounded number of times; that determines the traversal cost.
Check the problem constraints before deciding whether this complexity will pass.
Use this to learn the idea, then write your own version.
1#include <iostream>2#include <queue>3#include <vector>4 5using namespace std;6using ui = unsigned int;7 8int main() {9 ui h, w;10 cin >> h >> w;11 12 vector<string> g(h, string(w, '.'));13 vector<vector<int>> dist(h, vector<int>(w, -1));14 queue<pair<ui, ui>> q;15 16 for (ui i = 0; i < h; i++) {17 for (ui j = 0; j < w; j++) {18 cin >> g[i][j];19 if (g[i][j] == 'E') {20 q.push({i, j});21 dist[i][j] = 0;22 }23 }24 }25 26 vector<pair<int, int>> dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};27 while (!q.empty()) {28 auto [i, j] = q.front();29 q.pop();30 31 for (auto [di, dj] : dirs) {32 int ni = int(i) + di, nj = int(j) + dj;33 if (ni < 0 || ni >= int(h) || nj < 0 || nj >= int(w)) {34 continue;35 }36 if (g[ui(ni)][ui(nj)] == '.' && dist[ui(ni)][ui(nj)] == -1) {37 dist[ui(ni)][ui(nj)] = dist[i][j] + 1;38 q.push({ni, nj});39 }40 }41 }42 43 vector<string> ans(h, string(w, '#'));44 vector<char> dest = {'^', 'v', '<', '>'};45 for (ui i = 0; i < h; i++) {46 for (ui j = 0; j < w; j++) {47 if (g[i][j] == '.') {48 for (ui k = 0; k < 4; k++) {49 auto [di, dj] = dirs[k];50 int ni = int(i) + di, nj = int(j) + dj;51 if (ni < 0 || ni >= int(h) || nj < 0 || nj >= int(w)) {52 continue;53 }54 if (dist[ui(ni)][ui(nj)] == dist[i][j] - 1) {55 ans[i][j] = dest[k];56 break;57 }58 }59 } else if (g[i][j] == 'E') {60 ans[i][j] = 'E';61 }62 }63 }64 65 for (const auto& row : ans) cout << row << endl;66 67 return 0;68}