java中没有swap函数,也不能对字符串进行直接操作,所以改变x的位置的操作需要先转化为char数组,然后再手写swap函数,再用String的valueOf()方法将char数组转化为字符串保存
import java.util.*;
import java.io.*;
public class Main{
//本题难点需要进行状态更新,每次变换x的位置时,需要把当前状态记录下来,防止下次再次遍历出现死循环
//如果使用二维数组来保存数据,很难实现状态更新
static int[][] dir = {{-1,0},{0,1},{1,0},{0,-1}};
static Queue<String> qu = new LinkedList<String>();
static Map<String, Integer> map = new HashMap<String, Integer>();
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String st = br.readLine().replace(" ", "");
int stx=0,sty=0;
System.out.print(bfs(st));
}
public static int bfs(String st){
map.put(st, 0);
qu.add(st);
while(!qu.isEmpty()){
st = qu.poll();
if(st.equals("12345678x")) return map.get(st);
int dis = map.get(st);
int x = st.indexOf('x')/3;//将字符串转化为想象中的一个二维数组,记录x的横坐标
int y = st.indexOf('x')%3;//将字符串转化为想象中的一个二维数组,记录x的纵坐标
int xdis = st.indexOf('x');
char[] sc = st.toCharArray();
for(int i=0;i<4;i++){
int newx = x+dir[i][0],newy = y+dir[i][1];
if(newy<3&&newx>=0&&newx<3&&newy>=0){
char temp = sc[xdis];
sc[xdis]= sc[newx*3+newy];
sc[newx*3+newy] = temp;
if(!map.containsKey(String.valueOf(sc))) {//如果当前搜索的状态已经出现过那么久直接跳过,否则加入队列
map.put(String.valueOf(sc), dis+1);
qu.add(String.valueOf(sc));
}
temp = sc[xdis];
sc[xdis]= sc[newx*3+newy];
sc[newx*3+newy] = temp;
}
}
}
return -1;
}
}