The 8th Blue Bridge Cup 2017 - frog jumping cup

Title Description

It takes at least a few steps to ask , To jump into another target situation ?

Examples

Input ：
WWBB
WWBB
Output ：
2

Their thinking :

1.BFS Traverse all States , Storage status and its corresponding steps ;

2. If it is found to be consistent with the results, exit .

matters needing attention :

1. Use a dictionary to store a certain state and the corresponding number of steps , Easy to find duplicate status , Reduce time complexity ;

2. Do not use lists to store status , Because the list cannot be used as a dictionary key , And the application string ;

3.“ Jump cup ” The process can be implemented with a list .

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<>();// Store string , Can achieve the effect of checking whether it is repeated 
    public static void main(String[] args) {
    
        Scanner scan=new Scanner(System.in);
        String s1=scan.next();// The initial state 
        String s2= scan.next();// Target state 
        // Find the location of the empty cup 
        int ii=0;
        for (int i = 0; i < s1.length(); i++) {
    
            if(s1.charAt(i)=='*'){
    
                ii=i;
                break;
            }
        }
        // Search for 
        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()){
    
                    // Create a modified string 
                    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){
    
                        // Duplicate string appears 
                        continue;
                    }else{
    
                        map.put(news, 1);
                        node next=new node();
                        next.x=newx;
                        next.count= now.count+1;
                        next.s=news;
                        que.offer(next);
                    }
                }
            }
        }
        // Output the answer 
        System.out.println(answer);
        scan.close();
    }
}
class node{
    
    int x;// Coordinates of empty cup 
    int count;// They count 
    String s;// The current state of the string 
}