bfs 36pts 求调悬关
查看原帖
bfs 36pts 求调悬关
820707
Do_www楼主2024/3/29 16:47
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
const int N = 1005;
int k[N];
int n, a, b, ans;
bool st[N];

int bfs(int x, int id)
{
    queue<PII> q;
    q.push({a, 0});
    if(x == b) return 0;
    while(q.size())
    {
        auto t = q.front();
        q.pop();
        int x1 = t.first, y1 = t.second;
        if(x1 == b) return y1;
        int up = x1 + k[x1];
        int down = x1 - k[x1];
        if(up <= n  && !st[up]) 
        {
            st[up] = true;
            q.push({up, id + 1});
        }
        if(down >= 1 && !st[down])
        {
            st[down] = true;
            q.push({down, id + 1});
        }
    }
   return -1;
}

int main()
{
    cin >> n >> a >> b;
    for(int i = 1; i <= n; i ++) cin >> k[i];
    cout << bfs(a, 0) << endl;
    return 0;
}
2024/3/29 16:47
加载中...