广度优先搜索，深搜超时
需要判断界限，做标记，已到过的地点就不必去了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
53
54
55
56
57
58#include<cstdio>
#include<iostream>
using namespace std;
int head=0,tail=1;
int n,k;
int f[199999];
int d[9999999];
int t[9999999];
int bfs(int w)
{
d[1]=w;
while(head<tail)
{
head++;int x;
for(int i=1;i<=3;i++)
{
if(i==1) x=d[head]+1;
if(i==2) x=d[head]-1;
if(i==3) x=d[head]*2;
if(f[x]==0&&x>=0&&x<=100000)
{
f[x]=1;
d[++tail]=x;
t[tail]=t[head]+1;if(d[tail]==k) return t[tail];
}
}
/*if(f[d[head]+1]==0&&d[head]+1>0&&d[head]+1<100000)
{
f[d[head]+1]=1;
d[++tail]=d[head]+1;
t[tail]=t[head]+1;if(d[tail]==k) return t[tail];
}
if(f[d[head]-1]==0&&d[head]-1>0&&d[head]-1<100000)
{
f[d[head]-1]=1;
d[++tail]=d[head]-1;
t[tail]=t[head]+1;if(d[tail]==k) return t[tail];}
if(f[d[head]*2]==0&&d[head]*2>0&&d[head]*2<100000)
{
f[d[head]*2]=1;
d[++tail]=d[head]*2;
t[tail]=t[head]+1;if(d[tail]==k) return t[tail];}*/
}
return 0;
}
int main()
{
scanf("%d%d",&n,&k);
if(n>=k)
{
printf("%d",n-k);
return 0;
}
printf("%d",bfs(n));
return 0;
}
大老代码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#include<cstdio>
#include<iostream>
using namespace std;
int head=0,tail=1;
int n,k;
int f[199999];
int d[9999999];
int t[9999999];
int bfs(int w)
{
d[1]=w;
while(head<tail)
{
head++;int x;
for(int i=1;i<=3;i++)
{
if(i==1) x=d[head]+1;
if(i==2) x=d[head]-1;
if(i==3) x=d[head]*2;
if(f[x]==0&&x>=0&&x<=100000)
{
f[x]=1;
d[++tail]=x;
t[tail]=t[head]+1;if(d[tail]==k) return t[tail];
}
}
}
return 0;
}
int main()
{
scanf("%d%d",&n,&k);
if(n>=k)
{
printf("%d",n-k);
return 0;
}
printf("%d",bfs(n));
return 0;
}