AcWing 845. 八数码(API)
原题链接
中等
作者:
半透明の微笑
,
2024-04-11 17:19:43
,
所有人可见
,
阅读 3
import java.io.*;
import java.util.*;
public class Main{
static Queue<String> q = new LinkedList<>();
static HashMap<String, Integer> map = new HashMap<>();
static int[] dx = {0, 0, -1, 1};
static int[] dy = {-1, 1, 0, 0};
static String str;
static void swap(char[] c, int a, int b){
char t = c[a];
c[a] = c[b];
c[b] = t;
}
static int bfs(){
q.add(str);
map.put(str, 0);
while(!q.isEmpty()){
String t = q.poll();
char[] c = t.toCharArray();
if(t.equals("12345678x")) return map.get(t);
int idx = t.indexOf('x');
int x = idx / 3;
int y = idx % 3;
for(int i = 0; i < 4; i ++){
int xx = x + dx[i];
int yy = y + dy[i];
if(xx >= 0 && xx < 3 && yy >= 0 && yy < 3){
swap(c, idx, xx * 3 + yy);
String s = String.valueOf(c);
if(!map.containsKey(s)){
map.put(s, map.get(t) + 1);
q.add(s);
}
swap(c, idx, xx * 3 + yy);
}
}
}
return -1;
}
public static void main(String[] args)throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
str = br.readLine().replaceAll(" ","");
System.out.println(bfs());
}
}