BFS Catch That Cow

思路: 如果FJ在奶牛前面,那么只能往回走 否则就用BFS查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <iostream>
#include <queue>
using namespace std;

const int N = 100000000;
int vis[N];
int step[N];
int n,k;
void bfs(int n,int k) {
queue<int> q;
int now,next = 0;
q.push(n);
step[n] = 0;
vis[n] = 1;
while (!q.empty()) {
now = q.front();
q.pop();
for (int i = 0; i < 3; i++) {
if (i == 0) {
next = now - 1;
} else if(i == 1) {
next = now + 1;
} else {
next = now * 2;
}
if(next < 0 || next > N) continue;
if(!vis[next]) {
vis[next] = 1;
q.push(next);
step[next] = step[now] + 1;
}
if (next == k) {
cout << step[next];
return;
}
}
}
return ;
}

int main(int argc, const char * argv[]) {

int n,k;
cin >> n >> k;
if (n >= k) {
cout << n - k << endl;
} else {
bfs(n, k);
}

return 0;
}
script>