问题描述

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

　　我们把第一个图的局面记为：12345678.
　　把第二个图的局面记为：123.46758
　　显然是按从上到下，从左到右的顺序记录数字，空格记为句点。
　　本题目的任务是已知九宫的初态和终态，求最少经过多少步的移动可以到达。如果无论多少步都无法到达，则输出-1。

输入格式

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

输出格式

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

样例输入

12345678.
123.46758

样例输出

3

样例输入

13524678.
46758123.

样例输出

22

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();

    }

}