首页 > 代码库 > 算法笔记_183:历届试题 九宫重排(Java)

算法笔记_183:历届试题 九宫重排(Java)

目录

1 问题描述

2 解决方案

 


1 问题描述

问题描述
  如下面第一个图的九宫格中,放着 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();
    }
}

 

 

 

 

 

 

 

参考资料:

   1.蓝桥杯 历届试题 九宫重排 (广搜)

 

算法笔记_183:历届试题 九宫重排(Java)