AcWing 1100. 抓住那头牛(bfs)
原题链接
简单
作者:
白墙
,
2021-07-21 21:10:21
,
所有人可见
,
阅读 201
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int N = 2 * 1e5;
int dist[N];
int dx[] = {-1, 1};
bool st[N];
int n, k;
void bfs (int s) {
queue<int> q;
st[s] = true;
memset (dist, 0x3f,sizeof dist);
dist[s] = 0;
q.push(s);
bool flag = false;
while(q.size()) {
auto t = q.front();q.pop();
int x = t;
for (int i = 0; i < 2; i ++) {
int nx = x + dx[i];
if (nx <= 0 || nx > 100000) continue;//注意这里要限制一下,数组要开大一点,开成二倍
if (st[nx]) continue;
dist[nx] = dist[x] + 1;
st[nx] = true;
if (nx == k) {
flag = true;
break;
}
q.push(nx);
}
//这里第三种情况特判
if (flag) break;
int nx = x + x;
if (st[nx] || nx > 100000) continue;
dist[nx] = dist[x] + 1;
st[nx] = true;
if (nx == k) break;
q.push(nx);
}
}
int main () {
cin >> n >>k;
bfs(n);
cout << dist[k] << endl;
return 0;
}