文章
68
粉丝
691
获赞
26
访问
575.6k
求消耗最小的问题,一般都是bfs
#define ll int
#define inf 0x3ffffff
#define MAX 205
#define vec vector<ll>
ll N, A, B, K[MAX], res = inf, vis[MAX], step[MAX];
int main() {
cin >> N >> A >> B;
memset(vis, 0, sizeof(vis));
memset(step, 0, sizeof(vis));
for (int i = 1; i <= N; i++)cin >> K[i];
queue<ll> q; q.push(A); vis[A] = 1;
while (!q.empty()) {
ll v = q.front(); q.pop();
if (v == B) { res = step[B]; break; }
if (v + K[v] >= 1 && v + K[v] <= N && !vis[v + K[v]]) {
vis[v + K[v]] = 1; q.push(v + K[v]); step[v + K[v]] = step[v] + 1;
}
if (v - K[v] >= 1 && v - K[v] <= N && !vis[v - K[v]]) {
vis[v - K[v]] = 1; q.push(v - K[v]); step[v - K[v]] = step[v] + 1;
}
}
if (res == inf)cout << -1 << endl;
else cout << res << endl;
}
登录后发布评论
暂无评论,来抢沙发