蓝桥杯历届试题-九宫重排-题解（Java代码）带注释

解题思路:

双向宽度优先算法搜索，如果相遇了就说明找到了

注意事项:

记录每次扩展的节点是哪个方向的以及这个方向的层数

参考代码:

import java.util.*;

public class 双向BFS {
    // 队列,交替遍历初始状态和结果的扩展节点
    private static LinkedList<String> queue = new LinkedList<>();
    // 记录遍历的节点都是那一层的，这里有个小技巧，就是将开始状态设为第0层，
    // 将目标状态设为第1层，之后的子节点的值由父节点加一得到
    private static Map<String,Integer> tmap = new HashMap<>();
    // 记录节点是由开始状态扩展来的还是目标节点，1表示前者，2表示后者
    private static Map<String,Integer> smap = new HashMap<>();
    public static void main(String[] args){
        Scanner reader = new Scanner(System.in);
        String start = reader.next();
        String target = reader.next();
        System.out.println(BFS(start,target));
    }
    private static int BFS(String start,String target){
        if(start.equals(target))
            return 0;
        queue.add(start);
        queue.add(target);
        tmap.put(start,0);
        tmap.put(target,1);
        smap.put(start,1);
        smap.put(target,2);
        while (!queue.isEmpty()){
            String current = queue.pop();
            for(String next : findNext(current)){
                // 当一个方向出现重复的状态时舍弃，不加入队列中
                if(smap.getOrDefault(current,0) == smap.getOrDefault(next,0))continue;
                // 当扩展的节点存在，且这个存在的节点和当前节点不是一个方向的，说明找到了
                if(smap.getOrDefault(current,0) + smap.getOrDefault(next,0) == 3)
                    // 当前节点的层数与相遇节点的层数相加就是结果，若目标状态设的是第0层则需要再加一
                    return tmap.get(current) + tmap.get(next);
                // 把扩展接待你加入队列
                queue.add(next);
                // 得到这个节点的层数
                tmap.put(next,tmap.get(current)+1);
                // 得到这个节点是那个方向的
                smap.put(next,smap.get(current));
            }
        }
        // 没得到结果返回-1
        return -1;
    }
    // 获取扩展节点
    private static List<String> findNext(String current){
        List<String> list = new ArrayList<>();
        // 找到.的位置
        int i = current.indexOf(".");
        int row = i/3,col = i%3;
        int[] dx = {0,1,0,-1};
        int[] dy = {-1,0,1,0};
        // 找到与点可以交换的位置
        for(int k =0;k<4;k++){
            int x = row + dx[k],y = col +dy[k];
            if(x>=0 && x<=2 && y>=0 && y<=2){
                int index = x*3+y;
                //进行交换
                list.add(swap(current,i,index));
            }
        }
        return list;
    }
    private static String swap(String s,int a,int b){
        StringBuffer sb = new StringBuffer(s);
        char temp = sb.charAt(a);
        sb.setCharAt(a,sb.charAt(b));
        sb.setCharAt(b,temp);
        return sb.toString();
    }
}