文章

68

粉丝

691

获赞

26

访问

575.6k

头像
bfs-最短,最低耗搜索通解
P1072
发布于2020年5月10日 23:29
阅读数 10.5k

求消耗最小的问题,一般都是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;
}

 

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发