AcWing 1100. 抓住那头牛
原题链接
简单
作者:
王小强
,
2021-01-31 17:15:20
,
所有人可见
,
阅读 277
BFS 算法
#include <iostream>
#include <queue>
using namespace std;
const int N = 1E5;
int vis[N], n, k;
int bfs() {
queue<int> q{{n}};
vis[n] = 1; // mark as visited
int steps = 0;
while (not q.empty()) {
size_t sz = q.size();
while (sz--) {
int x = q.front(); q.pop();
// if (x == k) return steps;
for (const int nxt : { x - 1, x + 1, x << 1 }) {
if (nxt < 0 || nxt > N|| vis[nxt]) continue;
if (nxt == k) return steps + 1;
q.emplace(nxt);
vis[nxt] = 1; // mark as visited
}
}
++steps;
}
return -1;
}
int main(void) {
cin >> n >> k;
cout << bfs() << endl;
}