[noip模拟]计蒜姬BFS

Description

兔纸们有一个计蒜姬，奇怪的是，这个计蒜姬只有一个寄存器X。兔纸们每次可以把寄存器
中的数字取出，进行如下四种运算的一种后，将结果放回寄存器中。
1.X=X+X
2.X=X-X
3.X=X*X
4.X=X/X
已知初始时寄存器里的值为A，兔纸们想要知道，是否能通过若干次操作，使得最终寄存器
里的值是B。如果可能，它们还想知道最少的操作次数。

Input

包含两个正整数A，B。

1 ≤ A，B ≤ 1000000000

Output

一个整数，即最少操作次数，如果不存在方案，则输出-1。

Sample Input

3 4

Sample Output

3
//
第一次：3/3=1
第二次：1+1=2
第三次：2*2=4



------------------------------------------------------分割线-----------------------------------------
最近有一种一巴掌拍死自己的冲动，我刚刚开始看到这道题，心想简单呗，就是一个ＢＦＳ呗，最多加一点优化呗，于是两天过去了。。。。在我濒临崩溃之际，他终于过了

这道题虽然很简单，但是还是很有意思的，比较考思维，吃一蛰长一智，我很感谢自己把这道题坚持下来了
我一开始用的是很普通的BFS，一开始是超时，接着我把b为2的次方的情况给优化成O（1）的复杂度，但是还是要超时，百般无奈下，我看了题解
不得不说，很机智，反向BFS。。。。。。。
因为正向来的，a一不小心就会大于b，然后无限延伸下去，而反向来的话，当b到1就是极限了，所以总体来说的话缩小比加倍更加的优化
当我一个全新的程序出来以后，我还是一直WA，后来用Pascal程序提交算是过了，后来检查C++程序才终于发现，原来我忘了考虑a，b相等的情况

思路：反向缩小b，如果当

前值等于a就输出步数，值为1就输出步数+1，如果开平方和除以2都不能得到整数1就输出-1

我就提供一个反向BFS程序，正向的等我再去研究研究hash判重再说

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<iostream>
#include<cstdlib>
#include<cmath>
#define maxn 500000000
using namespace std;

int a,b;
struct node{
    int val,dep;
};
queue<node>q;

int check(node x)
{
    if(x.val==a)return x.dep;
    if(x.val==1)return x.dep+1;
    return 0;
}

int main()
{
    scanf("%d%d",&a,&b);
    if(a==b)
    {
        printf("0");return 0;
    }
    q.push((node){b,0});
    while(!q.empty())
    {
        node x=q.front();
        q.pop();
        if(x.val%2==0)q.push((node){x.val/2,x.dep+1});
        int nxt=floor(sqrt(x.val*1.0));
        if(pow(nxt,2)==x.val&&nxt!=1)q.push((node){nxt,x.dep+1});
        if(check(x)!=0){
            printf("%d",check(x));return 0;
        }
        
    }
    printf("-1");
}