Approach
Breadth-first search
For ABC007 C — 幅優先探索, 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
- 76 lines of C++ from the credited upstream file abc007_3.cpp.
- The implementation visibly relies on sequence storage, ordered lookup.
- 3 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 <cmath>2#include <iostream>3#include <map>4#include <tuple>5#include <vector>6 7using namespace std;8 9string to_key(unsigned int y, unsigned int x) {10 return to_string(y) + "-" + to_string(x);11}12 13void bfs(vector<vector<char>>& grid,14 vector<tuple<unsigned int, unsigned int>> cands, unsigned int l,15 vector<vector<unsigned int>>& visited) {16 if (cands.size() == 0) {17 return;18 }19 20 vector<tuple<unsigned int, unsigned int>> new_cands;21 map<string, bool> cands_map;22 for (auto& c : cands) {23 unsigned int y = get<0>(c);24 unsigned int x = get<1>(c);25 26 grid[y][x] = '#';27 visited[y][x] = min(visited[y][x], l);28 29 if (grid[y - 1][x] != '#' && !cands_map[to_key(y - 1, x)]) {30 new_cands.push_back({y - 1, x});31 cands_map[to_key(y - 1, x)] = true;32 }33 34 if (grid[y][x - 1] != '#' && !cands_map[to_key(y, x - 1)]) {35 new_cands.push_back({y, x - 1});36 cands_map[to_key(y, x - 1)] = true;37 }38 39 if (grid[y + 1][x] != '#' && !cands_map[to_key(y + 1, x)]) {40 new_cands.push_back({y + 1, x});41 cands_map[to_key(y + 1, x)] = true;42 }43 44 if (grid[y][x + 1] != '#' && !cands_map[to_key(y, x + 1)]) {45 new_cands.push_back({y, x + 1});46 cands_map[to_key(y, x + 1)] = true;47 }48 }49 50 bfs(grid, new_cands, l + 1, visited);51}52 53int main() {54 unsigned int r, c;55 cin >> r >> c;56 57 unsigned int sy, sx;58 cin >> sy >> sx;59 60 unsigned int gy, gx;61 cin >> gy >> gx;62 63 vector<vector<char>> grid(r + 2, vector<char>(c + 2, '#'));64 for (unsigned int y = 0; y < r; y++) {65 for (unsigned int x = 0; x < c; x++) {66 cin >> grid[y + 1][x + 1];67 }68 }69 70 vector<vector<unsigned int>> visited(r + 2,71 vector<unsigned int>(c + 2, r * c));72 vector<tuple<unsigned int, unsigned int>> cands = {{sy, sx}};73 bfs(grid, cands, 0, visited);74 75 cout << visited[gy][gx] << endl;76}