题目描述

在一个3×3的网格中，1~8这8个数字和一个“X”恰好不重不漏地分布在这3×3的网格中。

例如：

1 2 3
X 4 6
7 5 8

在游戏过程中，可以把“X”与其上、下、左、右四个方向之一的数字交换（如果存在）。

我们的目的是通过交换，使得网格变为如下排列（称为正确排列）：

1 2 3
4 5 6
7 8 X

例如，示例中图形就可以通过让“X”先后与右、下、右三个方向的数字交换成功得到正确排列。

交换过程如下：

1 2 3 1 2 3 1 2 3 1 2 3
X 4 6 4 X 6 4 5 6 4 5 6
7 5 8 7 5 8 7 X 8 7 8 X

把“X”与上下左右方向数字交换的行动记录为“u”、“d”、“l”、“r”。

现在，给你一个初始网格，请你通过最少的移动次数，得到正确排列。

输入格式

输入占一行，将3×3的初始网格描绘出来。

例如，如果初始网格如下所示：
1 2 3

x 4 6

7 5 8

则输入为：1 2 3 x 4 6 7 5 8
输出格式

输出占一行，包含一个字符串，表示得到正确排列的完整行动记录。

如果不存在解决方案，则输出”unsolvable”。

样例

输入样例：

2  3  4  1  5  x  7  6  8 

输出样例

ullddrurdllurdruldr

算法1

(Astar) $O()$

八数码问题。
先判断是否有解。
如果有解再用A*计算出答案

如何判断是否有解：
    正确排列的逆序对数量为0，
    左右交换不会更改逆序对数量，
    上下交换逆序对数量更改为偶数 
    计算排列中的逆序对数量，如果为偶数， 才存在解决方案

如何计算答案：
    使用A*算法，h(x)为每个格子回到正确位置最少需要交换的次数的和

时间复杂度

参考文献

C++ 代码

#include <iostream> 
#include <set> 
#include <map>
#include <queue>
#include <algorithm>

using namespace std;

typedef unsigned int uInt;

const int N = 181450;
const uInt goal = 6053444;
const int dr[] = {0, 0, 1, -1};
const int dc[] = {1, -1, 0, 0};

int p[9], a[3][3], tot = 0;
char ans[100];
map<uInt, int> info;

// 判断是否有解决方案 
bool isSolvable () {
    int cnt = 0;
    for (int i = 0; i < 9; i++) {
        if (p[i] == 8) continue;
        for (int j = i + 1; j < 9; j++) {
            if (p[j] == 8) continue;
            if (p[i] > p[j]) cnt++;
        }
    }
    return cnt % 2 == 0;
}

void intToArray (uInt num, int &x, int &y) {
    for (int i = 2; i >= 0; i--) {
        for (int j = 2; j >= 0; j--) {
            a[i][j] = num % 9;
            num /= 9;
            if (a[i][j] == 8) {
                x = i;
                y = j;
            }
        }
    }
}

uInt arrayToInt (int &h) {
    int num = 0;
    h = 0; 
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            h += abs(j - a[i][j] % 3) + abs(i - a[i][j] / 3);
            num = num * 9 + a[i][j];
        }
    }
    h /= 2;
    return num;
}

uInt arrayToInt () {
    int num = 0;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            num = num * 9 + a[i][j];
        }
    }
    return num;
}

void AStar (int start) {
    priority_queue<pair<int, int> > q;
    q.push(make_pair(0, start));
    info[start] = 0;
    uInt node1, node2;
    int x, y, nx, ny, g, h;
    while (true) {
        node1 = q.top().second; q.pop();
        g = info[node1] / 10;
        intToArray(node1, x, y);
        for (int i = 0; i < 4; i++) {
            nx = x + dr[i]; ny = y + dc[i];
            if (nx >= 0 && ny >= 0 && nx < 3 && ny < 3) {
                swap(a[x][y], a[nx][ny]);
                node2 = arrayToInt(h);
                if (!info.count(node2)) {
                    q.push(make_pair(-g - h - 1, node2));
                    info[node2] = (g + 1) * 10 + i; // 存储信息，包括花费和改变的方向 
                    if (node2 == goal) return;
                }
                swap(a[x][y], a[nx][ny]);
            }
        }
    }
}

int main () {
    char c;
    uInt start;
    for (int i = 0; i < 9; i++) {
        cin >> c;
        if (c != 'x') p[i] = c - '0' - 1;
        else p[i] = 8;
        a[i/3][i%3] = p[i];
    }
    if (isSolvable()) {
        int h, start = arrayToInt(), node = goal;
        if (start != goal) {
            AStar(start);
            int x = 2, y = 2;
            for (int i = 0; i < 9; i++) {
                a[i/3][i%3] = i;
            }
            for (; node != start; tot++) {
                int dir = info[node] % 10;
                switch (dir) {
                    case 0: ans[tot] = 'r'; break;
                    case 1: ans[tot] = 'l'; break;
                    case 2: ans[tot] = 'd'; break;
                    case 3: ans[tot] = 'u'; break;
                }
                swap(a[x][y], a[x-dr[dir]][y-dc[dir]]);
                x -= dr[dir];
                y -= dc[dir];
                node = arrayToInt();
            }
            for (int i = tot - 1; i >= 0; i--) {
                printf("%c", ans[i]);
            }
        }
    } else {
        printf("unsolvable\n");
    }
    return 0;
}