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

import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Scanner;

class per {
    public String str;
    public int step;

    public per(String str, int step) {
        this.str = str;
        this.step = step;
    }
}

public class 九宫重排 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String start = sc.nextLine();
        String end = sc.nextLine();

        LinkedList<per> list = new LinkedList<per>();//队列
        list.add(new per(start, 0));
        HashSet<String> set = new HashSet<String>();//去重
        set.add(start);

        while (!list.isEmpty()) {
            per p = list.poll();
            if (p.str.equals(end)) {//到达终点
                System.out.println(p.step);            
                return;
            }

            int index = p.str.indexOf(".");//寻找起点的位置
            int[] arr = f(index);//获取可以交换的位置
            for (int i = 0; i < arr.length; i++) {
                String a = swap(p.str.toCharArray(), index, arr[i]);//交换
                if (!set.contains(a)) {//避免重复运算
                    list.addLast(new per(a, p.step + 1));
                    set.add(a);
                }
            }
        }
        System.out.println(-1);
    }

    //根据.的下标获取可以交换的位置
    public static int[] f(int x) {
        if (x == 0) {
            return new int[] { 1, 3 };
        } else if (x == 1) {
            return new int[] { 0, 2, 4 };
        } else if (x == 2) {
            return new int[] { 1, 5 };
        } else if (x == 3) {
            return new int[] { 0, 4, 6 };
        } else if (x == 4) {
            return new int[] { 1, 3, 5, 7 };
        } else if (x == 5) {
            return new int[] { 2, 4, 8 };
        } else if (x == 6) {
            return new int[] { 3, 7 };
        } else if (x == 7) {
            return new int[] { 6, 4, 8 };
        } else {
            return new int[] { 5, 7 };
        }
    }

    public static String swap(char[] a, int x, int y) {
        char b = a[x];
        a[x] = a[y];
        a[y] = b;
        return String.valueOf(a);
    }

}