题目描述
小赵的实习转正答辩通过之后，小赵的Leader和他进行了一番沟通。Leader对小赵说，实习期间你有了很多进步已经能够独立负责日常工作了，已经是一个优秀的同学了。但是你应该延迟满足感，在日常工作之外应该更注重个人的成长，将自己作为一个产品去不断地迭代进步。反思之后小赵发现自己还是有很多不成熟的地方。
已知小赵当前的能力值是一个整数（不含前导零），每位数字都代表一个缺点。小赵希望自己能够不断进步成为一个成熟的韭菜，成熟的标志为小赵的能力值变成完全平方数。小赵可以通过圣杯直接删去能力值中某一位代表的缺点，如91可以删去1或9，来变成完全平方数。要求不能够删去所有的缺点，而且在删去某些位之后，剩下的数字不能有前导零。
但是使用圣杯要赢得圣杯战争才行，这就很麻烦。忙于古典文学的小赵希望用最少的次数成为成熟的韭菜。
输入
题目有多组测试数据，处理到文件结束。
每组数据一个整数n代表小赵的能力值。（0<=n<1e18）
输出
每组数据输出一个整数表示小赵最少要使用多少圣杯，如果不能满足条件则输出-1
样例输入
91
101
821
2
样例输出
1
2
1
-1
提示
91 —》 9
101 —》 1
821 —》 81
思路
利用bfs,将数加入队列，每次从队列中取出一个数，先判断这个数符不符合条件，符合就返回它所经历的消去的次数，不符合，就将这个数的各个位置的数字各消去一次后，再分别加入队列中（注意消去会不会出现前导零的情况）。
代码
#include<iostream>
#include<string>
#include<map>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
#include<iomanip>
#include<stack>
#include<cmath>
#include<fstream>
#define X first
#define Y second
#define best 131
#define INF 0x3f3f3f3f
#define P pair<int,int>
#define ls p<<1
#define rs p<<1|1
using namespace std
;
typedef long long ll
;
typedef unsigned long long ull
;
const double eps
=1e-5;
const double pai
=acos(-1.0);
const int N
=1e5+10;
const int maxn
=110;
const int mod
=1000000007;
struct node
{
ll x
;
int step
;
};
int bfs(ll x
)
{
node temp
;
temp
.x
=x
;
temp
.step
=0;
queue
<node
>q
;
q
.push(temp
);
while(q
.size())
{
node cur
=q
.front();
q
.pop();
if((ll
)sqrt(cur
.x
)*(ll
)sqrt(cur
.x
)==cur
.x
) return cur
.step
;
ll ant
=cur
.x
,cnt
=0,step
=cur
.step
;
while(ant
) ant
/=10,cnt
++;
if(cnt
==1) continue;
ll v
=cur
.x
,leave
=0,pre
=0,k
=1;
for(int i
=1;i
<=cnt
;i
++)
{
ll choice
=v
%10;
leave
=leave
+(choice
)*k
;
v
=v
/10;
q
.push({v
*k
+pre
,step
+1});
k
*=10;
pre
=leave
;
if(i
==cnt
-1&&choice
==0) break;
}
}
return -1;
}
int main()
{
ll n
;
while(~scanf("%lld",&n
))
{
printf("%d\n",bfs(n
));
}
return 0;
}
