九宫重排_康拓展开

历届试题九宫重排

时间限制：1.0s 内存限制：256.0MB

问题描述

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

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

输入格式

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

输出格式

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

样例输入

12345678.
123.46758

样例输出

样例输入

13524678.
46758123.

样例输出

拿到这个题的时候没什么思路，之前也做过bfs的题，最大的问题在于状态的保存，后来看到有个编码题用到了康拓展开，豁然开朗，数学真的是奇妙啊！还有很多不知道的东西呢！

又知道了java的几个坑，哪怕是数组直接赋值也是赋的地址，添加到链表之类的也是地址，想要不受干扰只能手工拷贝。

 package study_code;

 import java.util.LinkedList;

 import java.util.Queue;

 import java.util.Scanner;

 public class 八数码 {

     static int[] vis = new int [900900]; //判断哈希值是否被访问

     static int[] f = new int[9];    //保存阶乘

     static int end; //最终状态的哈希值

     static node start = new node();

     static String resPath;

     static int[][] dir = {{-1,0},{1,0},{0,-1},{0,1}};

     static char[] dirc = {'U','D','L','R'};

     static class node{

         int loc; //记录当前空格位置 用一个数字记录 1-9

         int s[]; //记录当前所有数字的位置

         int hashVal; //当前状态的哈希值

         String path = ""; //记录当前路径

         public node() {

         }

     }

     public static void fac() {

         f[0] = 1;

         for (int i = 1; i < f.length; i++) {

             f[i] = f[i-1] * i;

         }

     }

     //康拓展开

     public static int getHash(int[] s) {

         int res = 0;

         for (int i = 0; i < s.length; i++) {

             int index =0;

             for (int j = i+1; j < s.length; j++) {

                 if (s[j]<s[i]) {

                     index++;

                 }

             }

             res += index*f[9-1-i];

         }

         return res;

     }

     public static boolean bfs() {

         Queue<node> q = new LinkedList<node>();

         q.offer(start);

         vis[start.hashVal] = 1;

         while (!q.isEmpty()) {

             node cur = q.poll();

             vis[cur.hashVal] = 1;

             if (cur.hashVal == end) {

                 resPath = cur.path;

                 return true;

             }

             int x =cur.loc/3;

             int y =cur.loc%3;

             for (int i = 0; i < 4; i++) {

                 int tx = x + dir[i][0];

                 int ty = y + dir[i][1];

                 if (tx<0||ty<0||tx>=3||ty>=3) {

                     continue;

                 }

                 node temp = new node();

                 temp.loc = tx*3+ty;

                 temp.path = cur.path+dirc[i];

                 temp.s = cur.s.clone();

                 //交换空格的位置

                 temp.s[cur.loc] = temp.s[temp.loc];

                 temp.s[temp.loc] = 0;

                 temp.hashVal = getHash(temp.s);

                 if (vis[temp.hashVal] == 1) {

                     continue;

                 }

                 q.offer(temp);

                 vis[temp.hashVal] = 1;

             }

         }

         return false;

     }

     public static void main(String[] args) {

         Scanner sc = new Scanner(System.in);

         fac();

         String t = sc.nextLine();

         char[] c = t.toCharArray();

         int[] n = new int[c.length];

         for (int i = 0; i < c.length; i++) {

             if (c[i] == '.') {

                 n[i] = 0;

                 start.loc = i;

             }else {

                 n[i] = c[i] - '0';

             }

         }

         start.s = n.clone();

         start.hashVal = getHash(start.s);

         t = sc.nextLine();

         c = t.toCharArray();

         n = new int[c.length];

         for (int i = 0; i < c.length; i++) {

             if (c[i] == '.') {

                 n[i] = 0;

             }else {

                 n[i] = c[i] - '0';

             }

         }

         end = getHash(n);

         bfs();

         System.out.println(resPath.length());

     }

 }

巴特西

九宫重排_康拓展开_bfs

最新文章

热门文章