Java实现 蓝桥杯 历届试题 九宫重排
2023-09-14 08:58:12 时间
问题描述
如下面第一个图的九宫格中,放着 1~8 的数字卡片,还有一个格子空着。与空格子相邻的格子中的卡片可以移动到空格中。经过若干次移动,可以形成第二个图所示的局面。
我们把第一个图的局面记为:12345678.
把第二个图的局面记为:123.46758
显然是按从上到下,从左到右的顺序记录数字,空格记为句点。
本题目的任务是已知九宫的初态和终态,求最少经过多少步的移动可以到达。如果无论多少步都无法到达,则输出-1。
输入格式
输入第一行包含九宫的初态,第二行包含九宫的终态。
输出格式
输出最少的步数,如果不存在方案,则输出-1。
样例输入
12345678.
123.46758
样例输出
3
样例输入
13524678.
46758123.
样例输出
22
2 解决方案
本题下面代码参考自文末参考资料,本题的核心使用BFS求解,其中要求最小移动次数,在BFS遍历中,第一次达到匹配时就是最小移动次数,这个不好证明,不过可以自己细细想想,应该是这样。
该版本的C++版是100分,Java版为60分。
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Scanner;
public class Main {
public static String start, end;
public static int x1, y1; //起始就空格状态start中的空格子坐标
public static int[][] move = {{-1,0},{1,0},{0,-1},{0,1}};//表示分别向上、下、左、右移动一步
public static HashSet<String> set = new HashSet<String>(); //用于存放每次移动空格子后的结果,用于判重
static class Move { //内部类,存放空格子移动一步后的结果
public int x; //空格子位置横坐标
public int y; //空格子纵坐标移动步数
public int step; //记录最终
public String temp; //当前九宫格状态
public Move(int x, int y, int step, String temp) {
this.x = x;
this.y = y;
this.step = step;
this.temp = temp;
}
}
public void bfs() {
for(int i = 0;i < start.length();i++) { //寻找九宫格初始状态空格子的位置
if(start.charAt(i) == '.') {
x1 = i / 3;
y1 = i % 3;
}
}
ArrayList<Move> list = new ArrayList<Move>();
list.add(new Move(x1, y1, 0, start));
set.add(start);
while(!list.isEmpty()) {
Move now = list.get(0);
list.remove(0);
if(now.temp.equals(end)) { //当前状态为最终状态时,直接退出
System.out.println(now.step);
return;
}
for(int i = 0;i < 4;i++) { //四种行走方案
int x = now.x + move[i][0];
int y = now.y + move[i][1];
if(x < 0 || x > 2 || y < 0 || y > 2) //出现九宫格越界
continue;
int step = now.step + 1;
char n = now.temp.charAt(x * 3 + y); //获取当前行走的新位置字符
String temp0 = now.temp;
temp0 = temp0.replace(n, '-'); //交换'.'字符和n字符
temp0 = temp0.replace('.', n);
temp0 = temp0.replace('-', '.');
if(!set.contains(temp0)) { //判定当前行走结果是否已经行走过
set.add(temp0);
list.add(new Move(x, y, step, temp0));
}
}
}
System.out.println("-1");
return;
}
public static void main(String[] args) {
Main test = new Main();
Scanner in = new Scanner(System.in);
start = in.next(); //九宫格的初始状态
end = in.next(); //九宫格的最终状态
test.bfs();
}
}
相关文章
- java反转数组_Java实现数组反转翻转的方法实例
- java 登录 qq_Java实现QQ登录
- java 论坛_5 个最好用的 Java 开源论坛系统
- java 阶乘算法_Java 实现阶乘算法
- JAVA数据库连接池_java与数据库的连接怎么实现
- Java 近期新闻:MicroProfile 6.0、Kotlin 1.8、Spring Framework 升级
- Java学习笔记之九java二维数组及其多维数组的内存应用拓展延伸详解编程语言
- 实现Java程序操作MySQL数据库(java调用mysql)
- 深入浅出:利用Java操作MySQL(java操作mysql)
- Java 连接 MySQL 数据库简易实现(java连mysql)
- Oracle转Java实现跨平台开发的奇妙之旅(oracle转java)
- Java 连接 Redis:实现数据快速传输(java连redis)
- Java轻松使用Redis实现数据高效存储(java使用redis)
- Java脚本实现Linux系统的登录(java登录Linux)
- Java中使用Redis包实现高效缓存(redis包java)
- Java编程实现MySQL表备份(java备份mysql表)
- 使用Java连接SQL Server数据库,轻松实现数据交互(java连sqlserver)
- Linux平台上C语言接口调用Java语言实现(linux c调java)
- 在Linux上实现Java程序的运行(linux运行java程序)
- 使用Java语言写Redis实现一个分布式缓存系统(用java写个redis)
- Java存入Oracle数据库实现快速高效的数据存储(java存入oracle)
- 编程玩转Java之Oracle编程实战(java中的oracle)