青蛙跳杯子

解题思路:

通过BFS遍历所有情况，最先与结果匹配的那种情况，就是步数最少的情况。
注意事项:
1、这是个一维问题，青蛙移动规则可以抽象为空杯子的坐标变换，坐标变换量为{-3,-2,-1,1,2,3}（每次搜索都要依次试探这六种情况）

2、每次尝试有可能会出现之前已经出现过的字符串，这个时候所用的步数一定是大于之前那种情况的，所以碰到这种情况要直接跳过。代码中是通过HashMap来检查有没有重复的。

3、java无法直接改变字符串的某个字母，所以需要用到StringBuilder

4、构建node结构体，其中存储空杯子所在的位置，当前已经走了多少步以及，当前字符串的状态。
参考代码:

import java.util.*;

public class Main {
    public static int answer;
    public static int[] X={-3,-2,-1,1,2,3};
    public static Map<String,Integer> map=new HashMap<>();//存储字符串，可以达到检查是否重复的效果
    public static void main(String[] args) {
        Scanner scan=new Scanner(System.in);
        String s1=scan.next();//初始状态
        String s2= scan.next();//目标状态
        //找到空杯子的位置
        int ii=0;
        for (int i = 0; i < s1.length(); i++) {
            if(s1.charAt(i)=='*'){
                ii=i;
                break;
            }
        }
        //搜索
        node start=new node();
        start.count=0;  start.x=ii; start.s=s1;
        Deque<node> que=new LinkedList<>();
        que.offer(start);
        while(!que.isEmpty()){
            node now=que.poll();
            if(now.s.equals(s2)){
                answer= now.count;
                break;
            }
            for (int i = 0; i < 6; i++) {
                int newx= now.x+X[i];
                if(newx>=0&&newx<s1.length()){
                    //创建修改后的字符串
                    StringBuilder sb=new StringBuilder(now.s);
                    char temp= sb.charAt(now.x);
                    sb.setCharAt(now.x, sb.charAt(newx));
                    sb.setCharAt(newx,temp);
                    String news= sb.toString();
                    if(map.get(news)!=null){
                        //出现重复字符串
                        continue;
                    }else{
                        map.put(news, 1);
                        node next=new node();
                        next.x=newx;
                        next.count= now.count+1;
                        next.s=news;
                        que.offer(next);
                    }
                }
            }
        }
        //输出答案
        System.out.println(answer);
        scan.close();
    }
}
class node{
    int x;//空杯子所在坐标
    int count;//步数
    String s;//字符串当前状态
}