这个题我用的方法是bfs

其实是个模板题。对于每一个数我们可能有的操作是3种

1. 我们可以加 1
2. 我们可以减 1
3. 我们可以给这个数平方

因为我们的操作步数可以看作每个权值都是1，所以直接套bfs的模板就好了，对于每个数分别枚举三个方向，然后将符合范围的结果加入队列。

代码实现

n, m = map(int, input().split(' '))

d = [0 for i in range(2005)]
q = [n]

while len(q) > 0:
    
    x = q[0] + 1
    if x <= 2000 and d[x] == 0:
        d[x] = d[q[0]] + 1
        q.append(x)
        
    x = q[0] - 1
    if x >= 1 and d[x] == 0 :
        d[x] = d[q[0]] + 1
        q.append(x)
        
    x = q[0] * q[0]
    if x <= 2000  and d[x] == 0:
        d[x] = d[q[0]] + 1
        q.append(x)
    q.pop(0)

print(d[m])

小想法

其实加入这个数是小的，那么只有减法操作可以到达了，就直接输出差就好了。

#include <bits/stdc++.h> #define ll long long using namespace std; ll aa,bb,zx=2147480000,f[2000005]; void work(ll x,ll ans) { if(x>=bb) { zx=min(zx,ans+x-bb); return; } f[x]=1; if(x>1&&f[x-1]==0) work(x-1,ans+1); if(f[x+1]==0) work(x+1,ans+1); if(f[xx]==0&&x!=1) work(xx,ans+1); f[x]=0; } int main() { cin>>aa>>bb; work(aa,0); cout<<zx; return 0; }

数学方法和bfs方法

准备蓝桥杯，做到这一题之前是没有好好看过bfs的，虽然数据结构课上学过。。。一开始准备dfs解，但是好好想想发现完全不行，于是用数学的方法写了：

a,b=map(int,input().split())
bb,sta,s=0,0,0
bb=b
sta=b
count=1
ss=[1000,1000]
while sta!=1:
      k=int(sta**0.5)
      sta=k if abs(k**2-sta) < abs((k+1)**2-sta) else k+1
      if sta==1:
            break
      s=abs(sta**2-bb)+s
      ss.append(abs(a-sta)+s+count)
      bb=sta
      count=count+1
print(abs(min(b-a,min(ss)) ))

这种方法不是很好想，比赛没那个时间，还是bfs好用一点：

a,b=map(int,input().split())
l=[(a,0)]
ch=[1,-1]
dp=[0]*2000
for i in range(10000):
      if l[0][0]>2000:
            del(l[0])
            continue
      if l[0][0]<=0:
            del(l[0])
            continue     
      for i in ch:
            if dp[l[0][0]]==0:
                  l.append((l[0][0]+i,l[0][1]+1))
      if dp[l[0][0]]==0:
            l.append((l[0][0]*l[0][0],l[0][1]+1))
      if l[0][0]==b:                            ##终结判定
            print(l[0][1])
            break
      dp[l[0][0]]=1                             ##标记已经删除过，确定不是正确答案的一组
      del(l[0])