Approach
Breadth-first search
For ABC412 C — Giant Domino, 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
- 65 lines of C++ from the credited upstream file abc412_c.cpp.
- The implementation visibly relies on sequence storage, work queue.
- 7 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 <algorithm>2#include <iostream>3#include <queue>4#include <set>5#include <vector>6 7using namespace std;8 9using ll = long long;10 11int main() {12 ios_base::sync_with_stdio(false);13 cin.tie(nullptr);14 15 int t;16 cin >> t;17 18 while (t--) {19 int n;20 cin >> n;21 vector<ll> s(n + 1);22 23 for (int i = 1; i <= n; i++) cin >> s[i];24 25 if (n == 1) {26 cout << 1 << endl;27 continue;28 }29 30 multiset<pair<ll, int>> available;31 for (int i = 1; i <= n; i++) available.insert({s[i], i});32 33 vector<int> dist(n + 1, -1);34 queue<int> q;35 q.push(1);36 dist[1] = 1;37 available.erase(available.find({s[1], 1}));38 39 while (!q.empty() && dist[n] == -1) {40 int sz = q.size();41 for (int k = 0; k < sz; k++) {42 int u = q.front();43 q.pop();44 45 ll limit = 2LL * s[u];46 47 auto it = available.upper_bound({limit, n + 1});48 vector<multiset<pair<ll, int>>::iterator> to_remove;49 50 for (auto it2 = available.begin(); it2 != it; ++it2) {51 int v = it2->second;52 dist[v] = dist[u] + 1;53 q.push(v);54 to_remove.push_back(it2);55 }56 57 for (auto& iter : to_remove) available.erase(iter);58 }59 }60 61 cout << dist[n] << endl;62 }63 64 return 0;65}