【SCOI 2005】骑士精神

Solution

老年选手在线写搜索

感觉这题的估价函数有点不太对头，毕竟直接找不一样的也许会有找出来的四个棋子可以两两互换的情况。

(emm) 反正 (A) 了。

Code

#include <cstdio>
#include <iostream>
using namespace std;

int n = 5, dep, dir[10][10] = {{1, 2}, {1, -2}, {-1, 2}, {-1, -2}, {2, 1}, {2, -1}, {-2, 1}, {-2, -1}};
char g[10][10], goal[10][10];
bool f;

int read() {
    int x = 0, f = 1; char s;
    while((s = getchar()) < '0' || s > '9') if(s == '-') f = -1;
    while(s >= '0' && s <= '9') {x = (x << 1) + (x << 3) + (s ^ 48); s = getchar();}
    return x * f;
}

int check() {
    int cnt = 0;
    for(int i = 1; i <= n; ++ i)
        for(int j = 1; j <= n; ++ j)
            if(g[i][j] ^ goal[i][j]) ++ cnt;
    return cnt;
}

bool iddfs(const int s, const int x, const int y) {
    if(s == dep) {
        if(! check()) {f = 0; return 1;}
        return 0;
    }
    for(int i = 0; i < 8; ++ i) {
        int tx = x + dir[i][0];
        int ty = y + dir[i][1];
        if(tx < 1 || ty < 1 || tx > n || ty > n) continue;
        swap(g[x][y], g[tx][ty]);
        if(s + check() <= dep && iddfs(s + 1, tx, ty)) return 1;
        swap(g[x][y], g[tx][ty]);
    }
    return 0;
}

int main() {
    int sx, sy;
    for(int i = 1; i <= 3; ++ i)
        for(int j = 1; j <= n; ++ j)
            goal[i][j] = (j < i ? '0' : '1');
    for(int i = 4; i <= n; ++ i)
        for(int j = 1; j <= n; ++ j)
            goal[i][j] = (j <= i ? '0' : '1');
    goal[3][3] = '*';
    for(int T = read(); T; -- T) {
        dep = 0; f = 1;
        for(int i = 1; i <= n; ++ i) scanf("%s", g[i] + 1);
        for(int i = 1; i <= n; ++ i)
            for(int j = 1; j <= n; ++ j)
                if(g[i][j] == '*') {sx = i, sy = j; break;}
        while(dep < 15 && f) ++ dep, iddfs(0, sx, sy);
        if(! f) printf("%d
", dep);
        else puts("-1");
    }
    return 0;
}