「Luogu P2324」「SCOI2005」骑士精神

Description

在一个 $5 \times 5$ 的棋盘上有白色和黑色的骑士各 $12$ 个,以及一个空位(每个骑士都可以移动到和它横坐标相差 $2$,纵坐标相差 $1$ 或横坐标相差 $1$,纵坐标相差 $2$ 的空位上)。给定初始棋盘,求出至少移动多少次能得到目标棋盘(如下图)。如果 $15$ 步以内不能得到,输出 $-1$ 。

E5zvdO.png

Source

[Luogu]P2324

Solution

IDA* 经典题。

不管是 A* 还是 IDA*,最重要的就是 估价函数,定义为:

其中 $f(n)$ 是节点 $n$ 的估价函数,$g(n)$ 是当前的实际步数,$h(n)$ 是对未来步数的最完美估价。

为什么是这样呢?

假设你觉得到 $n$ 这个状态需要 $f(n)$ 步,你到当前状态已经花了 $g(n)$ 步,现在你想从当前状态到 $n$ 这个状态,在运气最好的情况下还需要 $h(n)$ 步。若 $g(n) + h(n) > f(n)$,则显然当前状态不能再 $f(n)$ 步之内到达 $n$ 这个状态。

如果要让所有马归位,状态数会非常多,所以我们考虑移动空位,即让空位与马交换位置,直到当前状态与目标状态相同。除此之外,这道题有要求 $15$ 步之内完成,所以可以 迭代加深,即规定最大深度,超过这个深度就直接退出。换句话说,我们可以把这个最大深度作为 $f(n)$ 。

本题中的 最完美估价

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
const int goal[MAXN + 1][MAXN + 1] = { //目标矩阵 
{ 0, 0, 0, 0, 0, 0 },
{ 0, 1, 1, 1, 1, 1 },
{ 0, 0, 1, 1, 1, 1 },
{ 0, 0, 0, -1, 1, 1 },
{ 0, 0, 0, 0, 0, 1 },
{ 0, 0, 0, 0, 0, 0 }
};

inline int h() {//最完美估价
int cnt = 0;
for (int i = 1; i <= 5; ++i)
for (int j = 1; j <= 5; ++j)
cnt += a[i][j] != goal[i][j];
//我们统计了当前状态与目标状态不同的位置个数为 cnt,
//但是我们实际要统计的是不在自己位置上的马的个数,
//这里我们把空位也算了进去,若所有马都在自己位置上,
//则此时空位也一定在自己的位置上,由此可得,
//空位对结果没有影响,所以最后 cnt 要 -1
return cnt - 1;
}

对于一匹不在自己位置上的马,在最优的情况下,我们只需要一次移动就能使这匹马归位。假设每一匹这样的马都需要移动一次,所以我们统计这样的马的个数即可。

还有一个剪枝,就是记录上一步是空格在哪个位置,下一步再跳回上一步的位置显然不优,这样可以少掉很多无用递归。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

template <class T>
inline void read(T &x) {
x = 0;
char c = getchar();
bool f = 0;
for (; !isdigit(c); c = getchar()) f ^= c == '-';
for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
x = f ? -x : x;
}

inline void readChar(char &c) {
for (c = getchar(); c != '0' && c != '1' && c != '*'; c = getchar());
}

template <class T>
inline void write(T x) {
if (x < 0) {
putchar('-');
x = -x;
}
T y = 1;
int len = 1;
for (; y <= x / 10; y *= 10) ++len;
for (; len; --len, x %= y, y /= 10) putchar(x / y + 48);
}

const int MAXN = 5;
const int dx[8] = { -2, -1, 2, 1, 2, 1, -1, -2 };
const int dy[8] = { 1, 2, 1, 2, -1, -2, -2, -1 };
const int goal[MAXN + 1][MAXN + 1] = { //目标矩阵,空位标记为 -1
{ 0, 0, 0, 0, 0, 0 },
{ 0, 1, 1, 1, 1, 1 },
{ 0, 0, 1, 1, 1, 1 },
{ 0, 0, 0, -1, 1, 1 },
{ 0, 0, 0, 0, 0, 1 },
{ 0, 0, 0, 0, 0, 0 }
};
int t, sx, sy, a[MAXN + 5][MAXN + 5];
bool sol;

inline int h() {//最完美估价
int cnt = 0;
for (int i = 1; i <= 5; ++i)
for (int j = 1; j <= 5; ++j)
cnt += a[i][j] != goal[i][j];
//我们统计了当前状态与目标状态不同的位置个数为 cnt,
//但是我们实际要统计的是不在自己位置上的马的个数,
//这里我们把空位也算了进去,若所有马都在自己位置上,
//则此时空位也一定在自己的位置上,由此可得,
//空位对结果没有影响,所以最后 cnt 要 -1
return cnt - 1;
}

void dfs(int x, int y, int g, int f, int prex, int prey) {
if (sol || x < 1 || x > 5 || y < 1 || y > 5 || g + h() > f) return;
if (h() == -1) {//若最完美估价为 -1,说明当前状态与目标状态重合
sol = 1;//标记为有解
return;
}
for (int i = 0; i < 8; ++i) {
int tx = x + dx[i], ty = y + dy[i];
if (tx == prex && ty == prey) continue;//保证下一步不与上一步相同
swap(a[x][y], a[tx][ty]);//空格与马交换位置
dfs(tx, ty, g + 1, f, x, y);//继续搜,当前步数 +1
swap(a[x][y], a[tx][ty]);//回溯
}
}

int main() {
for (read(t); t; --t) {
for (int i = 1; i <= 5; ++i)
for (int j = 1; j <= 5; ++j) {
char c;
readChar(c);
if (c == '*') {
sx = i, sy = j;//空位位置
a[i][j] = -1;//标记为 -1
} else a[i][j] = c ^ 48;//字符转成数字
}
int ans = -1;
for (int i = 0; i <= 15; ++i) {//迭代加深(规定深度搜索)
sol = 0;
dfs(sx, sy, 0, i, 0, 0);
if (sol) {
ans = i;//深度为 i 时有解
break;
}
}
write(ans);
putchar('\n');
}
return 0;
}

本文标题:「Luogu P2324」「SCOI2005」骑士精神

文章作者:Heartlessly

发布时间:2019年05月14日 - 07:19:30

最后更新:2019年05月14日 - 09:08:11

原始链接:https://heartlessly.github.io/problems/luogu-p2324/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

0%