ZHOJ_#20971.最快转换数字_广搜BFS

ZHOJ_#20971.最快转换数字_广搜BFS

#20971. 最快转换数字

• ID: 20971传统题1000ms256MiB尝试: 70已通过: 9难度: 8上传者:ZHtwinkle

Description

给你两个正整数 aa 和 bb（1≤a,b≤10001≤a,b≤1000），并且允许你进行如下操作：

1. 每次对 aa 加 11；
2. 每次对 aa 减 11；
3. 每次对 aa 进行平方操作，如 33 平方后变为 99。

现在请你求出将 aa 变成 bb 的最少操作次数是多少。

Format

Input

一行包含两个整数 aa和 bb，由空格隔开。

Output

一个整数，表示最少的操作次数。

Samples

输入数据 1

3 10

Copy

输出数据 1

2

// ZHOJ_#20971.最快转换数字_广搜BFS
#include
using namespace std;
 
const int N=1111;
int cnt[N];
int a,b,ans;
 
// 检查的是将要前往的点
// 用坐标点剪枝 而不是相对位置 
inline bool f_tt( int tt ) { return ( tt>=0 && tt<=1000 && cnt[tt]==0 ); }
 
void f()
{
    queue<int> q;
    q.push(a);
 
    while( !q.empty() )
    {
        int data=q.front(); q.pop();
        
        if( data==b ) { ans=cnt[data]; return ; }
 
        int tt;
        tt=data-1; if( f_tt(tt) ) { cnt[tt]=cnt[data]+1; q.push(tt); }
        tt=data+1; if( f_tt(tt) ) { cnt[tt]=cnt[data]+1; q.push(tt); }
        tt=data*data; if( f_tt(tt) ) { cnt[tt]=cnt[data]+1; q.push(tt); }
    }
}
 
int main()
{
    scanf("%d%d",&a,&b );
 
    if( a>=b )  ans=a-b;
    else        f();
    
    printf("%d\n",ans );
 
    return 0;
}