在一个3×3的网格中，1~8这8个数字和一个“X”恰好不重不漏地分布在这3×3的网格中。
例如：
1 2 3
X 4 6
7 5 8
在游戏过程中，可以把“X”与其上、下、左、右四个方向之一的数字交换（如果存在）。
我们的目的是通过交换，使得网格变为如下排列（称为正确排列）：
1 2 3
4 5 6
7 8 X
例如，示例中图形就可以通过让“X”先后与右、下、右三个方向的数字交换成功得到正确排列。
交换过程如下：
1 2 3 1 2 3 1 2 3 1 2 3
X 4 6 4 X 6 4 5 6 4 5 6
7 5 8 7 5 8 7 X 8 7 8 X
现在，给你一个初始网格，请你求出得到正确排列至少需要进行多少次交换。
输入格式
输入占一行，将3×3的初始网格描绘出来。
例如，如果初始网格如下所示：
1 2 3
x 4 6
7 5 8
则输入为：1 2 3 x 4 6 7 5 8
输出格式
输出占一行，包含一个整数，表示最少交换次数。
如果不存在解决方案，则输出”-1”。
输入样例：
2 3 4 1 5 x 7 6 8
输出样例
19 注意：StringBuilder比String要快思路：把8数码当成一个字符串处理
字符的位置-由一维字符串得到在3x3矩阵中的位置
然后对于四个方向广搜，交换字符的位置得到一个新的字符串
用map记录当前的状态，有的话就不能再走，没有则记录新状态 代码：
import java.util.ArrayDeque;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner; public class Main{
static Map<String,Integer> map=new HashMap<String, Integer>();
static ArrayDeque<String> q=new ArrayDeque<>();
static int dx[]={1,-1,0,0};
static int dy[]={0,0,1,-1};
static int bfs(String start){
q.offer(start);
map.put(start, 0); while(!q.isEmpty()){ String s=q.poll();
int distance=map.get(s);
if(s.equals("12345678x")) return distance; int k=s.indexOf('x');
int x=k/3,y=k%3;
for(int i=0;i<4;i++){
int xx=x+dx[i];
int yy=y+dy[i];
if(xx<0 || yy<0 || xx>=3 || yy>=3) continue; int ind=3*xx+yy;
char ch=s.charAt(ind);
StringBuilder ss= new StringBuilder();
for(int j=0;j<9;j++){
if(j==k) ss.append(ch);
else if(j==ind) ss.append("x");
else ss.append(s.charAt(j));
}
if(map.get(ss.toString())==null){
map.put(ss.toString(), map.get(s)+1);
q.offer(ss.toString());
}
}
}
return -1;
}
public static void main(String[] args) {
Scanner scan=new Scanner(System.in);
String start="";
for(int i=1;i<=9;i++){
String ch=scan.next();
start+=ch;
}
System.out.println(bfs(start));
}
}