[无聊君]蓝桥杯历届试题-九宫重排 简单题解，一次就过

解题思路:
一道简单的BFS（广度优先搜索）题目，套模板可直接解题

与输入地图的题目一样，只是将地图的位移数组

上 -1，0

下 1，0

左 0，-1

右 0，1

改为在字符串中模拟地图位移数组

上 -3

下 3

左 -1

右 1

注意事项:
虽然题目给的是一个3×3的地图

但是输入的是一个字符串

给出了开始和结束的情况
参考代码:

import java.util.LinkedList;
import java.util.Scanner;
import java.util.TreeSet;

public class 九宫重排 {
	private static class BFSNode {
		public String state;
		public int step;

		public BFSNode(String state, int step) {
			this.state = state;
			this.step = step;
		}
	}
	
	//开头
	public static void main(String[] args) {
		//接收
		Scanner sr = new Scanner(System.in);
		String start = sr.nextLine();
		String end = sr.nextLine();
		//建立队列
		LinkedList q = new LinkedList();
		TreeSet ts = new TreeSet();
		BFSNode root = new BFSNode(start, 0);
		//表头
		q.add(root);
		//查重放入表头
		ts.add(start);
		//移动数据的数组
		int[] move = new int[] { -3, -1, 1, 3 };
		//开始循环
		while (!q.isEmpty()) {
			//出队
			BFSNode currentNode = q.remove();
			//判断是否与输入的结果相同
			if (currentNode.state.equals(end)) {
				System.out.println(currentNode.step);
				break;
			}
			//判断当前 “.” 的位置
			int newkwz = currentNode.state.indexOf(".");
			//算出子节点
			for (int i = 0; i < move.length; i++) {
				//记录位置与移动数组结合后的位置
				int toto = newkwz + move[i];
				//判断数字交换是否符合交换规则
				if ( toto > 8 || toto < 0 || 
				(newkwz == 3 && move[i] == -1) || (newkwz == 5 && move[i] == 1) || 
				(newkwz == 2 && move[i] == 1) || (newkwz == 6 && move[i] == -1)   ) {
					toto = 0;
					continue;
				}
				//将字符串拆解进数组
				char[] arr = currentNode.state.toCharArray();
				//数组交换位置
				char temp = arr[newkwz];
				arr[newkwz] = arr[toto];
				arr[toto] = temp;
				//数组转换回字符串
				String newState = new String(arr);
				//查重 如果成功放入 TreeSet 中 将子节点放入列表 并且步数+1
				if (ts.add(newState)) {
					q.add(new BFSNode(newState, currentNode.step + 1));
				}
			}
		}
		//如果 循环结束并且队列为空 输出-1（没有方案可以转换到当前位置）
		if (q.isEmpty()) {
			System.out.println(-1);
		}
	}
}