「BZOJ 1085」「SCOI2005」骑士精神

Description

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

Source

[BZOJ]1085

Solution

IDA* 经典题。

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

$$f(n) = g(n) + h(n)$$

其中 $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)$ 。

本题中的 最完美估价：

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

#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;
}