一个标准解法

题目描述

在一个5×5的棋盘上有12个白色的骑士和12个黑色的骑士，且有一个空位。

在任何时候一个骑士都能按照骑士的走法（它可以走到和它横坐标相差为1，纵坐标相差为2或者横坐标相差为2，纵坐标相差为1的格子）移动到空位上。

给定一个初始的棋盘，怎样才能经过移动变成如下目标棋盘：为了体现出骑士精神，他们必须以最少的步数完成任务。

样例

2
10110
01*11
10111
01001
00000
01011
110*1
01110

算法 IDA*

当前格点与目标格点值相同，则距离为0，反之为1。

显然估计函数就是每个位置的距离和。

枚举每次跳的位置DFS即可。

搜索中用了三个优化：

1. 记录上一步的方向，在下次搜索跳过对称的方向
2. 在进入下一层前，计算估计函数的变化
3. 当前深度+ 估计函数大于已搜索到的解，剪枝。

当估计函数为0时，搜索结束。

C++ 代码

#include <iostream>

using namespace std;

typedef pair<int, int> PII;

const int N = 5;

char g[5][9];

int ans, target[N][N] = {{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 cur[N][N], dx[] = {-1, -2, -2, -1, 1, 2, 2, 1}, dy[] = {2, 1, -1, -2, -2, -1, 1, 2};

inline bool check(int x, int y) {
    return 0 <= x && x < N && 0 <= y && y < N;
}

void dfs(PII s, int depth, int pre, int dist) {
    if (depth + dist >= ans) return;
    if (dist == 0) {
        ans = depth;
        return;
    }
    for (int i = 0; i < 8; i++) {
        if ((i + 4) % 8 == pre) continue;
        int x = s.first + dx[i], y = s.second + dy[i];
        if (check(x, y)) {
            int d1 = cur[x][y] != target[x][y];
            int d2 = cur[x][y] != target[s.first][s.second];
            swap(cur[s.first][s.second], cur[x][y]);
            dfs({x, y}, depth + 1, i, dist + d2 - d1);
            swap(cur[s.first][s.second], cur[x][y]);
        }
    }
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        for (int i = 0; i < N; i++) {
            cin >> g[i];
        }
        PII s;
        int d = 0;
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++) {
                if (g[i][j] == '*') {
                    s = {i, j};
                    cur[i][j] = 2;
                } else {
                    cur[i][j] = g[i][j] - '0';
                    d += cur[i][j] != target[i][j];
                }
            }
        ans = 16;
        dfs(s, 0, -10, d);
        if (ans == 16) puts("-1");
        else cout << ans << endl;
    }
    return 0;
}