D 清楚姐姐跳格子

题目

清楚正在玩跳格子游戏。地上有 个格子，清楚一开始在 号格子，目标是 号格子。
第 个格子上有一个数字 ，清楚在这个格子上可以往左右两边选一个方向，然后选择 的一个正整数因子作为长度，进行一次跳跃，但是不可以跳出边界。
请问清楚最少跳多少步，就可以到达 号格子。

输入

第一行输入一个整数 代表格子数量。
第二行输入 个整数 代表格子上的数字。

思路

1. 容易被的范围吓到
2. 对于,它能跳到的格子就可以直接连一条边
3. 发现边权都一样
4. 转换成了一个有向图最短路的问题
5. 虽然很大，但是最多就1000步，枚举步数，看是不是因子就好，最多的复杂度

代码

#include <bits/stdc++.h>
#define endl '\n'
//#define int long long
using ld = long double;
using lli = long long;
using ull = unsigned long long;
const int maxn = 1004;
typedef std::pair<int, int> pair;
lli steps[maxn];
int ans[maxn];
lli n = 0, t = 0, y = 0, m = 0;
std::queue<int> que;
void bfs(int s)
{
    ans[s] = 0;
    que.push(s);
    while(!que.empty())
    {
        t = que.front();
        que.pop();
        y = steps[t];
        m = std::min(n, y);
        for (lli i = 1; i <= m; i++)
        {
            if (y % i != 0) continue;
            if (t - i >= 1 && ans[t - i] == -1)
            {
                ans[t - i] = ans[t] + 1;
                que.push(t - i);
            }
            if (t + i <= n && ans[t + i] == -1)
            {
                ans[t + i] = ans[t] + 1;
                que.push(t + i);
            }
        }
    }
}

void solve()
{
    std::cin >> n;
    for (int i = 1; i <= n; i++)
    {
        std::cin >> steps[i];
    }
    memset(ans, -1, sizeof(ans));
    bfs(1);
    std::cout << ans[n] << endl;
}


signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    int t = 1;
    //std::cin >> t;
    while(t--)
    {
        solve();
    }
    return 0;
}