题目描述
在一个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;
}