本文共 940 字，大约阅读时间需要 3 分钟。

正题

题目大意

$n$次询问，给出一个数$x$，每次可以进行操作

1. 修改其中一个位，去掉前导零
2. 删掉其中一个位，去掉前导零

询问最少步骤使得$x$变为一个完全平方数

解题思路

我们可以从完全平方数开始广搜，操作变为

1. 加入一个数
2. 修改一个数

即可

$code$

#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;const int N=1e6+10;int T,f[N],w[1100],ans,k;bool v[N],z[N];queue
       
         q;void bfs(){
   	while(!q.empty()){
   		int x=q.front();k++;		q.pop();		for(int i=1;i<=1e5;i*=10){
   			for(int k=0;k<10;k++){
   				int y=x;y=y/i*i*10+y%i+k*i;				if(y>=1e6||v[y])continue;				q.push(y);v[y]=1;				f[y]=f[x]+1;			}		}		for(int i=1;i<=x;i*=10){
   			for(int k=0;k<10;k++){
   				if(i*10>x&&k==0)continue;				int y=x;y=y-y/i%10*i+k*i;				if(v[y])continue;				q.push(y);v[y]=1;				f[y]=f[x]+1;			}		}	}}int main(){
   	scanf("%d",&T);	for(int i=1;i*i<1e6;i++)		q.push(i*i),v[i*i]=1;	bfs(); 	for(int i=1;i<=T;i++){
   		int x;scanf("%d",&x);		if(x==1e6)printf("0\n");		else printf("%d\n",f[x]);	}}
       
      
     
    
   

转载地址：http://ddwaf.baihongyu.com/