Java实现 蓝桥杯 算法提高 八数码(BFS)

试题 算法提高 八数码

问题描述

  RXY八数码

输入格式

  输入两个33表格

  第一个为目标表格

  第二个为检索表格

输出格式

  输出步数

样例输入

1 2 3

4 5 6

7 8 0

1 2 3

4 5 6

7 0 8

样例输出

1

数据规模和约定

  3
3*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;
}
}
上一篇:Thinkphp文件上传


下一篇:从远程oracle上导入到本地同一张表中不存在的记录的方法