SCOI2005骑士精神

发表于 更新于 分类于 阅读次数：

Luogu P2324 [SCOI2005]骑士精神 把输入的棋子还原成题目要求的状态，求最小步数 第一次写IDA*，有点小激动www 如果考虑骑士（和马走法一样）的移动，情况过于复杂。发现只有一个空白位置，可以考虑移动空白位置 题目要求求出步数，而变换情况过多，难以直接搜索 这时候，迭代加深DFS就可以派上用场了，限定步数搜索，枚举$i = 1$到$i = 15$即可

并且，显然爆搜是布星的，结合估价函数，使用IDA*算法 从图中看出黑骑士白骑士排列顺序，把黑骑士标记为1，白骑士标记为0（对应题目输入），空格标记为2,则可以得到目标状态 每次移动只可以移动一个骑士，每有一个骑士不在目标颜色，就要多移动至少一次

设计估价函数$f(x) = d(x) + dep$，其中$d(x)$表示有几处不同，$dep$表示目前步数，明显有与实际步数$g(x)$比，有$f(x) \leq g(x)$，可以使用 设计出以下代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int a[5][5];
int value[5][5] = {
    { 1, 1, 1, 1, 1 },
    { 0, 1, 1, 1, 1 },
    { 0, 0, 2, 1, 1 },
    { 0, 0, 0, 0, 1 },
    { 0, 0, 0, 0, 0 }
};
int judge()
{
    int sum = 0;
    for (rint i = 0; i < 5; ++i) for (rint j = 0; j < 5; ++j)
        if (a[i][j] != value[i][j])
            ++sum;
    return sum;
}

有了IDA*核心的估价函数，写出暴力DFS即可 完整代码如下：

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
#include <bits/stdc++.h>
using namespace std;

int a[5][5];

int value[5][5] = {
    { 1, 1, 1, 1, 1 },
    { 0, 1, 1, 1, 1 },
    { 0, 0, 2, 1, 1 },
    { 0, 0, 0, 0, 1 },
    { 0, 0, 0, 0, 0 }
};

int judge()
{
    int sum = 0;
    for (int i = 0; i < 5; ++i) for (int j = 0; j < 5; ++j)
        if (a[i][j] != value[i][j])
            ++sum;
    return sum;
}

bool ok;
int ans;
int dx[] = { 1, 1, 2, 2, -1, -1, -2, -2 },
    dy[] = { 2, -2, 1, -1, 2, -2, 1, -1 };

void dfs(int dep, int x, int y, int max_dep)
{
    if (dep == max_dep) {
        if (judge() == 0) {
            ok = true;
            ans = max_dep;
        }
        return;
    }
    for (int i = 0; i < 8; ++i) {
        int nx = x + dx[i], ny = y + dy[i];
        if (nx < 0  ny < 0  nx > 4  ny > 4)
            continue;
        swap(a[x][y], a[nx][ny]);
        if (dep + judge() <= max_dep)
            dfs(dep + 1, nx, ny, max_dep);
        if (ok) return;
        swap(a[x][y], a[nx][ny]);
    }
}

int main()
{
    int T; cin >> T;
    while (T--) {
        char c; int x, y;
        for (int i = 0; i < 5; ++i) {
            for (int j = 0; j < 5; ++j) {
                cin >> c;
                if (c == '*') {
                    a[i][j] = 2;
                    x = i;
                    y = j;
                } else {
                    a[i][j] = c - '0';
                }
            }
        }
        if (judge() == 0) {
            printf("0\n");
            continue;
        }
        ans = -1; ok = false;
        for (int i = 1; i <= 15; ++i) {
            dfs(0, x, y, i);
            if (ok) break;
        }
        printf("%d\n", ans);
    }
    return 0;
}