BFS（广度优先搜索） 隐式最短路径问题

算法类型：BFS（广度优先搜索） 最短路径问题

题目特征：两种操作、最少步数、状态转换

难度等级：⭐⭐⭐ ✅ 这道题教会我们什么 隐式图的BFS：图不是预先画好的，边是动态生成的

状态空间思维：把问题转化为"状态+操作"的模型

细节决定成败：边界条件、个位判断、MAX设定都是坑

模板化思考：BFS题型都有固定套路，背熟模板能解决一大类问题

##题目简述：a通过 (反转) 操作或者 (＋k) 操作，变成b 的最短操作数

代码：

import java.util.*;
import java.io.*;
public class Main{
    static final int MAX=2000000;
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        PrintWriter out=new PrintWriter(System.out);
        int t=sc.nextInt();
        while(t-->0){
            int a,b,k;
            a=sc.nextInt();
            b=sc.nextInt();
            k=sc.nextInt();
            out.println(bfs(a,b,k));
        }
        out.flush();
    }
    static int bfs(int a,int b,int k){
        if(a==b)return 0;
        int[] dist=new int[MAX+1];
        Arrays.fill(dist,-1);
        Queue<Integer>q=new LinkedList<>();
        dist[a]=0;
        q.offer(a);
        
        while(!q.isEmpty()){
            int cur=q.poll();
            if(cur%10!=0){
                int rev=reverse(cur);
                
                if(rev<MAX&&dist[rev]==-1){
                    if(rev==b)return dist[cur]+1;
                    dist[rev]=dist[cur]+1;               
                    q.offer(rev);
                }
            }
            int add=cur+k;
            if(add<MAX&&dist[add]==-1){
                
                if(add==b)return dist[cur]+1;
                dist[add]=dist[cur]+1;
                q.offer(add);
            }
            
        }
        return -1;
    }
    static int reverse(int x){
        int res=0;
        while(x!=0){
            res=x%10+res*10;
            x/=10;
        }
        return res;
        
    }
}