#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#define pr 107

using namespace std;

struct Queue{int a,b,d;}q[2100000];
bool e[15000000];
void Inp(int a,int b,int d,int h)
{
     e[pr*a+b]=true;q[h].a=a;q[h].b=b;q[h].d=d;
}
int main()
{
    int p;
    scanf("%d",&p);
    q[1].a=1;q[1].b=0;q[1].d=0;e[q[1].a*pr+q[1].b]=true;
    int h=0,t=1;
    while(h<t)
    {
              h++;
              if(q[h].a==p)
              {
                           printf("%d",q[h].d);
                           break;
              }
              int aa,bb,a=q[h].a,b=q[h].b;
              aa=a<<1;bb=b;
              if(!e[pr*aa+bb]&&aa<=40000&&bb<=200)Inp(aa,bb,q[h].d+1,++t);
              aa=a<<1;bb=a;
              if(!e[pr*aa+bb]&&aa<=40000&&bb<=200)Inp(aa,bb,q[h].d+1,++t);
              aa=max(a,b<<1);bb=min(a,b<<1);
              if(!e[pr*aa+bb]&&aa<=40000&&bb<=200)Inp(aa,bb,q[h].d+1,++t);
              aa=b<<1;bb=b;
              if(!e[pr*aa+bb]&&aa<=40000&&bb<=200)Inp(aa,bb,q[h].d+1,++t);
              aa=a+b;bb=a;
              if(!e[pr*aa+bb]&&aa<=40000&&bb<=200)Inp(aa,bb,q[h].d+1,++t);
              aa=a+b;bb=b;
              if(!e[pr*aa+bb]&&aa<=40000&&bb<=200)Inp(aa,bb,q[h].d+1,++t);
              aa=max(a-b,b);bb=min(a-b,b);
              if(!e[pr*aa+bb]&&aa<=40000&&bb<=200)Inp(aa,bb,q[h].d+1,++t);
              aa=max(a-b,a);bb=min(a-b,a);
              if(!e[pr*aa+bb]&&aa<=40000&&bb<=200)Inp(aa,bb,q[h].d+1,++t);
    }
    return 0;
}

• Re:Hash爆搜500MS (3) yzx_H2O 2017-02-17 15:51:40