[SCOI 2005] 骑士精神

OI
  1. 1. 题意
  2. 2. 题解
    1. 2.1. 估价函数
  3. 3. 代码

题意

题目地址:BZOJCH luogu

要将棋盘上的马归位,求最小步数

题解

那就。。搜呗

首先注意到大力BFS会爆,大力DFS也会爆

然后再注意到题目中的条件限制:最多不超过15步

这已经很明显了,来写IDA*

那。。什么是IDA*呢?

迭代加深搜索。

好像。。很迷。。。

其实就是从小到大枚举走几步可以到终点,然后开始xjb搜,如果超过限制就return,直到搜到终点。

那么对于这个题,我们就枚举一下跳几步可以到达终点,从小到大来,每次dfs一下。

那么。。为什么要这样搞呢?

我们想要求最少的移动次数,如果单纯dfs是无法做到的,只能迭代加深。

这还没有完,只是IDA*的一部分,还有一顿操作在等着你。

估价函数

什么是估价函数呢?

对于当前的一个状态,给它一个评估。

那。。这有什么用呢?

我们到达每一个状态时,判断一下它已经跳的步数,再加上它的估价函数值,如果大于了限制,就大力return。

听上去好像很棒的样子,不过估价函数是不能xjb选的。

估价函数需要满足以下要求:可以估小,不可以估大

这是很显然的。

对于这个题目,我们可以以“不在自己位置上的马的个数”为估价函数,正确性可以自己脑补(跳一次最多复位一个马)。

当然如果要更优,可以以:“不在自己位置上的马跳回自己位置的步数和”为估价函数,据说更快。

注意到一次跳一个棋子,两个状态的估价函数是可以互相递推的,只需要看跳了之后的变化,如果大力每次计算,会T成70分

然后记得要维护一下,如果某一个地方已经搜到解了,就不必再搜下去了。

代码

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
//
// Created by Margatroid on 2017/10/12.
//

#include <bits/stdc++.h>
using namespace std;
typedef array<array<int, 5>, 5> board;
const board final_status = {1, 1, 1, 1, 1, -1, 1, 1, 1, 1, -1, -1, 0, 1, 1, -1, -1, -1, -1, 1, -1, -1, -1, -1, -1};
const int dx[] = {-2, -1, 1, 2, 2, 1, -1, -2},
dy[] = {1, 2, 2, 1, -1, -2, -2, -1};
inline int val(const board &status)
{
int ans = 0;
for (int i = 0; i < 5; ++i)
for (int j = 0; j < 5; ++j)
if (status[i][j] != final_status[i][j])
++ans;
return ans;
}
int sum = 0;
bool dfs(const board &now, int cost_limit, int step, int now_val)
{
if (now == final_status) return sum = step, true;
if (step + now_val > cost_limit + 1) return false;
board d = now;
int x, y;
for (int i = 0; i < 5; ++i)
for (int j = 0; j < 5; ++j)
if (d[i][j] == 0)
{
x = i, y = j;
goto label;
}
label:
bool status = 0;
for (int i = 0; i < 8; ++i)
{
if (x + dx[i] >= 5 || x + dx[i] < 0 || y + dy[i] >= 5 || y + dy[i] < 0) continue;
int nx = dx[i] + x, ny = dy[i] + y, new_val = now_val;
swap(d[x][y], d[nx][ny]);
if (d[x][y] == final_status[x][y] && d[nx][ny] != final_status[x][y]) --new_val;
else if (d[x][y] != final_status[x][y], d[nx][ny] == final_status[x][y]) ++new_val;
if (d[nx][ny] == final_status[nx][ny] && d[x][y] != final_status[nx][ny]) --new_val;
else if (d[nx][ny] != final_status[nx][ny] && d[x][y] == final_status[nx][ny])++new_val;
status |= dfs(d, cost_limit, step + 1, new_val);
swap(d[x][y], d[nx][ny]);
if (status) return status;
}
return status;
}
int ida_star(const board &start_status)
{
int ans = 1, st;
sum = 0;
for (; !(st = dfs(start_status, ans, 0, val(start_status))) && ans <= 15; ++ans);
if (st == 1 && ans <= 15)
return sum;
else
return -1;
}
int main()
{
int t;
cin >> t;
while (t--)
{
board now;
for (int i = 0; i < 5; ++i)
{
string s;
cin >> s;
for (int j = 0; j < 5; ++j)
{
char t = s[j];
if (t == '0')
now[i][j] = -1;
else if (t == '1')
now[i][j] = 1;
else if (t == '*')
now[i][j] = 0;
}
}
if (now == final_status)
{
cout << 0 << '\n';
continue;
}
cout << ida_star(now) << '\n';
}
}

我是菜,真的,这玩意写了一下午+一晚上。。。菜的扣jue qwq