AcWing 845. 八数码-java
原题链接
中等
作者:
Astarion
,
2021-02-12 10:37:06
,
所有人可见
,
阅读 282
import java.io.*;
import java.util.*;
class Main {
static final String END = "12345678x";
static int[] mx = {-1,0,1,0};
static int[] my = {0,-1,0,1};
static int getLocation(int x, int y) {
return x*3 + y;
}
static String swap(String state, int a, int b, int x, int y) {
int locationA = getLocation(a,b);
int locationX = getLocation(x,y);
char c = state.charAt(locationA);
char[] cs = state.toCharArray();
cs[locationA] = 'x';
cs[locationX] = c;
return new String(cs);
}
static int bfs(String start) {
Queue<String> queue = new ArrayDeque<>();
Map<String,Integer> map = new HashMap<>();
queue.add(start);
map.put(start,0);
while (!queue.isEmpty()) {
String state = queue.poll();
if (state.equals(END)) {
return map.get(state);
}
int location = state.indexOf("x");
int x = location/3; int y = location%3;
for (int i = 0; i < 4; i++) {
int a = x + mx[i];
int b = y + my[i];
if (a<0 || b<0 || a>2 || b>2) continue;
String newState = swap(state,a,b,x,y);
if (!map.containsKey(newState)) {
map.put(newState,map.get(state)+1);
queue.add(newState);
}
}
}
return -1;
}
public static void main(String[] args) throws IOException {
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader in = new BufferedReader(isr);
String start = in.readLine().replaceAll(" ","");
in.close();
isr.close();
System.out.println(bfs(start));
}
}