基础课(只需要输出步长)
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());
}
}
提高课(需要输出步长和路径)
只需要在基础课代码上修改一下map的value属性即可
import java.io.*;
import java.util.*;
public class Main{
static Queue<String> q = new LinkedList<>();
//map的value同时记录步数和路径
static HashMap<String, PII> map = new HashMap<>();
static int[] dx = {0, 0, -1, 1};
static int[] dy = {-1, 1, 0, 0};
static String[] way = {"l","r","u","d"};
static String str;
static void swap(char[] c, int a, int b){
char t = c[a];
c[a] = c[b];
c[b] = t;
}
static String bfs(){
q.add(str);
map.put(str, new PII(0, ""));//一点小修改
while(!q.isEmpty()){
String t = q.poll();
char[] c = t.toCharArray();
if(t.equals("12345678x")) return map.get(t).y;
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, new PII(map.get(t).x + 1, map.get(t).y + way[i]));//一点小修改
q.add(s);
}
swap(c, idx, xx * 3 + yy);
}
}
}
return "unsolvable";
}
public static void main(String[] args)throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
str = br.readLine().replaceAll(" ","");
System.out.println(bfs());
}
}
class PII{
int x;
String y;
public PII(int x, String y){
this.x = x;
this.y = y;
}
}