2024-11-12

九宫重排

1464138053

不得不说的八数码之九宫重排
距离第七届蓝桥杯决赛还有2天
问题描述

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

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

输入格式
输入第一行包含九宫的初态，第二行包含九宫的终态。
输出格式
输出最少的步数，如果不存在方案，则输出-1。
样例输入

12345678.
123.46758

样例输出

样例输入

13524678.
46758123.

样例输出

解题思路

由此题可以联想到八数码问题,百度查了资料有各种A各种IDA等等解法

此题我先使用了BFS，发现有两个问题，第一是状态转换，二是状态的标记，很麻烦

网上有种标记法是康托展开，是根据a10!+a21!+a32!+a43!+…+a9*8!相加得出的hash值

这个hash值就是当前表示的状态，那么就很方便了

后来我用了5的次方根表示hash码，运算速度比上面的hash快一倍，但是发现有一组测试数据不通过，所以生成的hash还不是唯一的，不能使用

我用的是a15^0+a25^1+a35^2+…+a95^8

那么状态的转换又是一个问题，Java没有C语言C++那么有个swap函数，一开始我用了原来状态每次进行状态变换

发现最后全部值都为0！这是一个很严重的问题，原来每次都没有把值给换过来，后来想了想用了个备份临时数组每次获取他对他进行操作

Oh yeah~终于搞掂晒

后来又用了Java集合类HashMap+BFS双搜算法，速度明显快很多

BFS双搜算法是两个队列分别从起始状态跟目标状态开始，然后每次都相互判断Hash码是否存在以达到可通行出路，即互通状态
BFS+Hash 实现代码

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

/**

BFS+HASH 九宫重排
@author Ape

/
public class BfsHash {
static final int MAX = 3;
static final int[] hash = { 1, 1, 2, 6, 24, 120, 720, 5020, 40320 }; // Hash生成规则
static int[][] dir = new int[][] { { 1, 0 }, { 0, 1 }, { 0, -1 }, { -1, 0 } }; // 移动规则
static int[] vis = new int[400000];
static int ans, sx, sy;
static BfsHash a = new BfsHash();

class Node {

int[][] map = new int[MAX][MAX];
int x, y, hash, h; // h为深度,即步数

// map的备份,切记不能直接进行复制
int[][] getCopyMap() {
    int[][] copy = new int[MAX][MAX];
    for (int i = 0; i < MAX; i++)
        for (int j = 0; j < MAX; j++)
            copy[i][j] = map[i][j];
    return copy;
}

Node() {
}

Node(int x, int y, int h, int[][] map, int hash) {
    this.x = x;
    this.y = y;
    this.h = h;
    this.map = map;
    this.hash = hash;
}

}

// 检查越界
static boolean check(int x, int y) {

if (x < 0 || y < 0 || x >= MAX || y >= MAX)
    return false;
return true;

}

// 生成Hash码,康托展开
static int getHash(int[][] map) {

int[] t = new int[MAX * MAX];
int k = 0, tHash = 0;
for (int i = 0; i < MAX; i++)
    for (int j = 0; j < MAX; j++)
        t[k++] = map[i][j];
for (int i = 0; i < 9; i++) {
    k = 0;
    for (int j = 0; j < i; j++)
        if (t[i] < t[j])
            k++;
    tHash += k * hash[i];
}
return tHash;

}

static int getHash2(int[][] map) {

int hash = 0, k = 1;
for (int i = 0; i < MAX; i++)
    for (int j = 0; j < MAX; j++) {
        hash += k * map[i][j];
        k *= 5;
    }
return hash;

}

static int bfs(Node start) {

Queue<Node> queue = new LinkedList<Node>();
queue.offer(start);
Node top = a.new Node();
int tx, ty, thash, th;
while (!queue.isEmpty()) {
    top = queue.poll(); // 出列
    if (top.hash == ans)
        return top.h;
    for (int i = 0; i < 4; i++) {
        tx = top.x + dir[i][0];
        ty = top.y + dir[i][1];
        if (!check(tx, ty))
            continue;
        // TODO 注意,切记不能直接get原来的map,而且复制map的时候不能直接赋值给一个数组,要遍历赋值
        // TODO
        // 因为直接拿原来的map下一次循环的top.map就不说出列时候的那个,所以每次换位都需要一个临时的数组,并生成hash
        int[][] tmap = top.getCopyMap();
        tmap[top.x][top.y] = tmap[tx][ty];
        tmap[tx][ty] = 0;
        thash = getHash(tmap);
        if (vis[thash] == 0) {
            th = top.h + 1;
            vis[thash] = 1; // 标记
            queue.offer(a.new Node(tx, ty, th, tmap, thash)); // 入列,要重新new一个
        }
    }
}
return -1;

}

// 字符串转int数组
static int[][] string2int(String string) {

char[] ch = string.toCharArray();
int[][] m = new int[MAX][MAX];
for (int i = 0; i < ch.length; i++)
    if (ch[i] != '.')
        m[i / 3][i % 3] = ch[i] - '0';
    else {
        m[i / 3][i % 3] = 0;
        // 起始空格位置
        sx = i / 3;
        sy = i % 3;
    }
return m;

}

public static void main(String[] args) {

Scanner scanner = new Scanner(System.in);
String start = scanner.next();
String end = scanner.next();
Node s = a.new Node();
Node e = a.new Node();
s.map = string2int(start);
s.hash = getHash(s.map);
s.x = sx;
s.y = sy;
vis[s.hash] = 1;

e.map = string2int(end);
e.hash = getHash(e.map);
ans = e.hash; // ans为目标状态的hash值

System.out.println(bfs(s));
scanner.close();

}

BFS双向搜索代码实现

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

/**

九宫重排
@author Ape

/
public class JiuGong {

static HashMap<String, Integer> hash1, hash2; // 使用Java集合类的MapHash
static int sx, sy, ex, ey, index;
static char[][] start = new char[3][3], end = new char[3][3];
static String startString, endString;
static int[][] dir = new int[][] { { 1, 0 }, { 0, 1 }, { 0, -1 }, { -1, 0 } }; // 移动规则

public static void main(String[] args) {

Scanner scanner = new Scanner(System.in);
startString = scanner.next();
endString = scanner.next();
long a = System.currentTimeMillis();
index = 0;
for (int i = 0; i < 3; i++)
    for (int j = 0; j < 3; j++) {
        start[i][j] = startString.charAt(index);
        end[i][j] = endString.charAt(index);
        if (start[i][j] == '.') {
            sx = i;
            sy = j;
        }
        if (end[i][j] == '.') {
            ex = i;
            ey =  ;
        }
        index++;
    }
Node node1 = new Node(start, sx, sy, 0);
Node node2 = new Node(end, ex, ey, 0);
Queue<Node> queue1 = new LinkedList<Node>();
Queue<Node> queue2 = new LinkedList<Node>();
hash1 = new HashMap<String, Integer>();
hash2 = new HashMap<String, Integer>();
hash1.put(startString, 0);
hash2.put(endString, 0);
queue1.offer(node1);
queue2.offer(node2);
System.out.println(bfs(queue1, queue2));
System.out.println(System.currentTimeMillis() - a);
scanner.close();

}

static boolean check(int x, int y) {

if (x < 0 || y < 0 || x >= 3 || y >= 3)
    return false;
return true;

}

static int bfs(Queue queue1, Queue queue2) {

while (!queue1.isEmpty() || !queue2.isEmpty()) {
    if (!queue1.isEmpty()) {
        Node node1 = queue1.poll(); // 出列
        if (hash2.containsKey(node1.getMapString())) // 判断hash2是否存在该状态
            return node1.getCount() + hash1.get(node1.getMapString());
        int x = node1.getX();
        int y = node1.getY();
        for (int i = 0; i < 4; i++) {
            int tx = x + dir[i][0];
            int ty = y + dir[i][1];
            if (!check(tx, ty))
                continue;
            char[][] t = node1.getCopyMap();
            t[x][y] = t[tx][ty];
            t[tx][ty] = '.';
            Node n = new Node(t, tx, ty, node1.getCount() + 1);
            String s = n.getMapString();
            if (hash2.containsKey(s))
                return n.getCount() + hash2.get(s);
            if (!hash1.containsKey(s)) {
                hash1.put(s, n.getCount());
                queue1.offer(n);
            }
        }
    }
    if (!queue2.isEmpty()) {
        Node node2 = queue2.poll(); // 出列
        if (hash1.containsKey(node2.getMapString())) // 判断hash1是否存在该状态
            return node2.getCount() + hash1.get(node2.getMapString());
        int x = node2.getX();
        int y = node2.getY();
        for (int i = 0; i < 4; i++) {
            int tx = x + dir[i][0];
            int ty = y + dir[i][1];
            if (!check(tx, ty))
                continue;
            char[][] t = node2.getCopyMap();
            t[x][y] = t[tx][ty];
            t[tx][ty] = '.';
            Node n = new Node(t, tx, ty, node2.getCount() + 1);
            String s = n.getMapString();
            if (hash1.containsKey(s))
                return n.getCount() + hash1.get(s);
            if (!hash2.containsKey(s)) {
                hash2.put(s, n.getCount());
                queue2.offer(n);
            }
        }
    }
}
return -1;

}

class Node {
char[][] map = new char[3][3];
int x, y, count;

public Node(char[][] map, int x, int y, int count) {
    super();
    this.map = map;
    this.x = x;
    this.y = y;
    this.count = count;
}

// 字符数组转成字符串
public String getMapString() {
    StringBuffer sb = new StringBuffer("");
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++)
            sb.append(map[i][j]);
    return sb.toString();
}

public char[][] getCopyMap() {
    char copy[][] = new char[3][3];
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++)
            copy[i][j] = map[i][j];
    return copy;
}

public char[][] getMap() {
    return map;
}

public void setCMap(char[][] map) {
    this.map = map;
}

public int getX() {
    return x;
}

public void setX(int x) {
    this.x = x;
}

public int getY() {
    return y;
}

public void setY(int y) {
    this.y = y;
}

public int getCount() {
    return count;
}

public void setCount(int count) {
    this.count = count;
}

}

测试数据

起始状态目标状态步数 BFS+Hash BFS双搜
12345678. 123.46758 3 0ms 0ms
13524678. 46758123. 22 119ms 19ms
12345678. 152743.86 6 0ms 0ms
.14276385 12345678. 26 240ms 41ms

20步以上的差距明显…