原题
题意
人在n点处，要抓在k点处的牛，可以从当前点i到i+1或者i-1或者i*2，求最短距离
分析
简单BFS每个条件，三个状态，第一次到达某一点就把当前这一点标记为经过，并从他的源头那一点更新当前点的最小步数，直到找到第k点。
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
| #include <bits/stdc++.h>
using namespace std;
int vis[100007],d[100007];
void bfs(int n,int k){
queue<int> q;
int now;
memset(vis,0,sizeof(vis));
memset(d,0,sizeof(d));
q.push(n);
vis[n]=1;
while(!q.empty()){
now=q.front();
q.pop();
if(now==k){
break;
}
if(now-1>=0&&!vis[now-1]){
q.push(now-1);
vis[now-1]=1;
d[now-1]=d[now]+1;
}
if(now+1<100007&&!vis[now+1]){
q.push(now+1);
vis[now+1]=1;
d[now+1]=d[now]+1;
}
if((now<<1)<100007&&!vis[now<<1]){
q.push(now<<1);
vis[now<<1]=1;
d[now<<1]=d[now]+1;
}
}
}
int main()
{
int n,k;
while(scanf("%d%d",&n,&k)!=EOF){
bfs(n,k);
printf("%d\n",d[k]);
}
}
|
