试题 算法提高 八数码
问题描述
RXY八数码
输入格式
输入两个33表格
第一个为目标表格
第二个为检索表格
输出格式
输出步数
样例输入
1 2 3
4 5 6
7 8 0
1 2 3
4 5 6
7 0 8
样例输出
1
数据规模和约定
33*2
PS:
花里胡哨得，直接套代码搜
import java.util.*;
public class Main {
static int[]dx = {0,0,1,-1};
static int[]dy = {1,-1,0,0};
static int[][]st = new int[3][3];
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
int [][]st1 = new int[3][3];
for(int i=0;i<3;++i){
for(int j=0;j<3;++j){
st1[i][j]=scan.nextInt();
}
}
for(int i=0;i<3;++i){
for(int j=0;j<3;++j){
st[i][j]=scan.nextInt();
}
}
System.out.println(bfs(st1));
}
public static int[][] swap(int[][]st1,int i,int j,int sx,int sy){
int[][]st2 = new int[3][3];
for(int w=0;w<3;++w){
for(int e=0;e<3;++e){
st2[w][e]=st1[w][e];
}
}
int x = st2[i][j];
st2[i][j]=st1[sx][sy];
st2[sx][sy]=x;
return st2;
}
public static int bfs(int[][]st1){
Queue<int[][]> q = new LinkedList<>();
HashMap<int[][],Integer> m = new HashMap<>();
q.offer(st1);
m.put(st1, 0);
while(!q.isEmpty()){
int[][]st2 = q.poll();
boolean b1 = true;
for(int w=0;w<3;++w){
for(int e=0;e<3;++e){
if(st2[w][e]!=st[w][e]){
b1=false;
}
}
}
if(b1){
return m.get(st2);
}
for(int i=0;i<3;++i){
for(int j=0;j<3;++j){
if(st2[i][j]==0){
for(int k=0;k<4;++k){
int sx = i+dx[k];
int sy = j+dy[k];
if(sx<0||sx>=3||sy<0||sy>=3){
continue;
}
int[][]st3=swap(st2,i,j,sx,sy);
if(!m.containsKey(st3)){
q.offer(st3);
m.put(st3, m.get(st2)+1);
}
}
}
}
}
}
return -1;
}
}