P2324 [SCOI2005]骑士精神¶

T22:05:00+08:00 洛谷：P2324 SCOI2005骑士精神 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

Lv0 暴力大法师 0pts¶

由于要求得最小的步数，使用 dfs 的话就只有全部跑完才能确定得到的结果是最小的结果。

C++
const int dx[] = {0, 1, 1, -1, -1, 2, 2, -2, -2};
const int dy[] = {0, 2, -2, 2, -2, 1, -1, 1, -1};

int ans = 16;

void dfs(int x, int y, int depth = 0) {
    if (depth > 15) return;
    if (check()) {
        ans = min(ans, depth-1);
        return;
    }
    for (int i = 1; i <= 8; i++) {
        int xx = x + dx[i];
        int yy = y + dy[i];
        if (xx < 1 || xx > 5 || yy < 1 || yy > 5) continue;
        swap(m[xx][yy], m[x][y]);
        dfs(xx, yy, depth+1);
        swap(m[xx][yy], m[x][y]);
    }
}

而每一步决策有 8 个方向，这颗树的增长速度十分恐怖 \(8^n\)，而最大步数为 15，那么就需要 \(8^{15}\) 次才能得到结果，绝对超时。

Lv1 迭代加深 20pts¶

考虑到答案可能在较低层中，而由于深搜的特点，到最深层才会返回，这样会多搜很多东西。

于是可以考虑限制搜索深度，迭代放宽深度。

C++
int ans = 16;

void dfs(int x, int y, int maxdepth, int depth = 0) {
    if (depth > maxdepth) return;
    // ...
}

int main () {
    // ...
    for (int i = 1; i <= 15; i++) {
        dfs(x, y, i);
        if (ans < 16) break;
    }
    // ...
}

然而这种“优化”也只能保证答案在较低层时不会超时，若答案在最深层，仍然要遍历所有状态才能得到结果。

Lv2 结合估价函数 —> IDA* 100pts¶

考虑有这样一个函数：

\[ f(x) = g(x) + h(x) \]

其中 \(g\) 为距离起点的距离函数，\(h\) 为距离终点的距离函数。

那么很显然，结合迭代加深，如果当前的 \(f\) 大于了 \(maxdepth\)，那么不能在限定步数内到达终点。

然而我们并不知道确切的 \(h\)，所以我们可以找出一个能够估计到终点的距离函数 \(h^*(x) \leq h(x)\)，保证小于等于是由于为防止估计错误而使 \(f\) 比实际大而导致判断不能到达。

针对本题来说，不难想到一个 \(h^*(x) = 不在原位置的棋子数（不包括空位）\)，可以想象一个最理想的过程，当前空位依次移动到每一个不在原位置的棋子处，每一次移动归位一个棋子。

完整代码：

C++
#include <iostream>

using namespace std;

char m[6][7];
const char goal[6][7] = {
    {"000000"},
    {"011111"},
    {"001111"},
    {"000*11"},
    {"000001"},
    {"000000"},
};

char read() {
    char c;
    while ((c = getchar()) != '0' && c != '1' && c != '*');
    return c;
}

const int dx[] = {0, 1, 1, -1, -1, 2, 2, -2, -2};
const int dy[] = {0, 2, -2, 2, -2, 1, -1, 1, -1};

int eval() {
    int cnt = 0;
    for (int i = 1; i <= 5; i++) {
        for (int j = 1; j <= 5; j++) {
            if (m[i][j] != goal[i][j]) cnt++;
        }
    }
    return cnt ? cnt-1 : 0;
}

int ans;

void dfs(int x, int y, int maxdepth, int depth = 0) {
    int e = eval();
    if (depth + e > maxdepth) return;
    if (!e) {
        ans = min(ans, depth);
        return;
    }
    for (int i = 1; i <= 8; i++) {
        int xx = x + dx[i];
        int yy = y + dy[i];
        if (xx < 1 || xx > 5 || yy < 1 || yy > 5) continue;

        swap(m[xx][yy], m[x][y]);
        dfs(xx, yy, maxdepth, depth+1);
        swap(m[xx][yy], m[x][y]);
    }
}


int main() {
    int T; cin >> T;

    int x, y;
    while (T--) {
        ans = 16;

        for (int i = 1; i <= 5; i++) {
            for (int j = 1; j <= 5; j++) {
                m[i][j] = read();
                if (m[i][j] == '*') {
                    x = i;
                    y = j;
                }
            }
        }

        for (int i = 1; i <= 15; i++) {
            dfs(x, y, i);
            if (ans < 16) break;
        }

        cout << (ans < 16 ? ans : -1) << endl;

    }

    return 0;
}

P2324 [SCOI2005]骑士精神¶

Lv0 暴力大法师 0pts¶

Lv1 迭代加深 20pts¶

Lv2 结合估价函数 —> IDA* 100pts¶

评论