3 条题解
-
0
#include <cstdio> #include <vector> #include <queue> #include <utility> #include <functional> using namespace std; int main() { int n, a, b; scanf("%d %d %d", &n, &a, &b); vector<int> arr(n + 1); for (int i = 1; i <= n; ++i) scanf("%d", &arr[i]); long long res = 1e9; vector<char> ita(n + 1, 0); // dfs 好像不行, 这样只有80分 // long long now = 0; // function<void(int)> dfs = [&](int i) { // 递归爆炸 // if (i <= 0 || i > n || ita[i]) // return; // // if (i == b) { // res = min(res, now); // return; // } // // ++now; // ita[i] = 1; // dfs(i + arr[i]); // dfs(i - arr[i]); // ita[i] = 0; // --now; // }; queue<pair<int, long long>> Q; // 当前是第几层 , 操作次数 Q.push({a, 0}); while (Q.size()) { auto x = Q.front(); int cen = x.first; long long cs = x.second; Q.pop(); if (cen == b) { res = cs; break; } if (cen + arr[cen] <= n && !ita[cen + arr[cen]]) { ita[cen + arr[cen]] = 1; Q.push({cen + arr[cen], cs + 1}); } if (cen - arr[cen] > 0 && !ita[cen - arr[cen]]) { ita[cen - arr[cen]] = 1; Q.push({cen - arr[cen], cs + 1}); } } // dfs(a); printf("%lld\n", res == 1e9 ? -1 : res); return 0; }
信息
- ID
- 85
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 7
- 标签
- 递交数
- 411
- 已通过
- 98
- 上传者