蓝桥杯_九宫重排 java

题目描述

如下图的九宫格中，放着 1 ~ 8 的数字卡片，还有一个格子空着。与空格子相邻的格子中的卡片可以移动到空格中。 经过若干次移动，可以形成图 2 所示的局面。

我们把上图的局面记为：12345678.

把下图的局面记为：123.46758

显然是按从上到下，从左到右的顺序记录数字，空格记为句点。

题目的任务是已知九宫的初态和终态，求最少经过多少步的移动可以到达。如果无论多少步都无法到达，则输出 -1。

输入描述

输入第一行包含九宫的初态，第二行包含九宫的终态。

输出描述

输出最少的步数，如果不存在方案，则输出 -1。

输入输出样例

示例

输入

12345678.
123.46758

输出

3

运行限制

• 最大运行时间：2s

• 最大运行内存: 256M

代码:

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Scanner;public class 九宫重排 {static int x1, y1;static HashSet set = new HashSet<>();//存放每次移动空格后的结果，用于判重static int[][] dir = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };public static void main(String[] args) {Scanner scanner = new Scanner(System.in);String start = scanner.next();String end = scanner.next();bfs(start, end);}private static void bfs(String start, String end) {for (int i = 0; i < start.length(); i++) {if (start.charAt(i) == '.') {// 记录空格位置x1 = i / 3;y1 = i % 3;}}ArrayList list = new ArrayList<>();list.add(new Node(x1, y1, 0, start));set.add(start);while (!list.isEmpty()) {Node 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 + dir[i][0];int y = now.y + dir[i][1];//处理边界if (x < 0 || x > 2 || y < 0 || y > 2) {continue;}// 获取当前行走后的新字符char n = now.temp.charAt(x * 3 + y);//获取当前九宫格状态String temp0 = now.temp;//交换temp0 = temp0.replace(n, '-');temp0 = temp0.replace('.', n);temp0 = temp0.replace('-', '.');//判断当前结果是否已经走过if (!set.contains(temp0)) {int step = now.step + 1;//步数 +1set.add(temp0);list.add(new Node(x, y, step, temp0));}}}System.out.println(-1);}
}class Node {int x;int y;int step;String temp;public Node(int x, int y, int step, String temp) {super();this.x = x;this.y = y;this.step = step;this.temp = temp;}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！