洛谷 P2685 [USACO07OPEN]抓牛Catch That Cow 广搜

洛谷 P2685 [USACO07OPEN]抓牛Catch That Cow

这里如果能够*2的话其实没几步就行了

因为相当于二进制倍增
然而如果 x 较大的移到较小的那么要移动好几步，这时候不能够乘2 ，我们步数直接特判一下就行了
然后每一步的增长空间都是指数级别的，这样就会RE了
然后不仅如此，他还不能走到负数的区域，否则也会因为不断扩张而导致RE
所以设计一个边界防止无限扩张而导致RE

 1 #include <cstdio>
 2 #include <cstdlib>
 3 using namespace std ;
 4 
 5 int x,y,h,t ; 
 6 struct node{
 7     int wei,step ;
 8 };
 9 node q[8000011] ;
10 int f[8000011] ;
11 
12 inline bool check(int x) 
13 {
14     return (x>=0&&x<=100000) ;
15 }
16 
17 inline void bfs(int x,int y) 
18 {
19     q[++t].wei = x ;
20     q[t].step = 0 ;
21     if(x==y) 
22     {
23         printf("0
") ;
24         return ;
25     }
26     while(1) 
27     {
28         ++h ;
29         int x = q[h].wei ;
30         if(!f[x+1]&&check(x+1)) q[++t].wei = x+1,q[t].step = q[h].step+1,f[x+1]=q[t].step ;
31         if(!f[x-1]&&check(x-1)) q[++t].wei = x-1,q[t].step = q[h].step+1,f[x-1]=q[t].step ;
32         if(!f[2*x]&&check(2*x)) q[++t].wei = 2*x,q[t].step = q[h].step+1,f[2*x]=q[t].step ;
33         if(f[y]) {
34             printf("%d
",f[y]) ;
35             return ;
36         }
37     }
38     
39 }
40 
41 int main() 
42 {
43     scanf("%d%d",&x,&y) ;
44     if(x>=y) printf("%d
",x-y) ; 
45             else bfs(x,y) ; 
46     
47     return 0 ;
48 }