[BZOJ 1085] [SCOI2005]骑士精神

Posted on | In , | Views:

前言

现在的$OI$这种搜索题已经很久没有出现过了，也只有在刷前些年的题才能看到了。

题目链接

BZOJ 1085

做法

第一反应想到状压，但是状态数至少也是$\binom{25}{12}*25$，是在太大了。
那只能搜索了，看到这道题显然是一个迭代加深的模型，所以我们考虑用$IDA^*$来解决。
考虑如何构造估价函数，最优情况下，我们每次能把一个黑棋或者白棋直接移到我们想要的位置上，所以我们对比一下期望棋盘和现在棋盘有几个位置不一样就行了。注意要把空格的贡献去掉，因为一次移动可能是空格和最后一个棋子同时归位。
那么接下来就是直接暴力搜索，枚举跳哪个骑士并不好，我们改为枚举跳空格就行了。
具体实现的话可以见代码。

代码

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
79
80
81
82
83
84
85
86
87
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<cstring>
#include<iostream>
#include<cmath>
#define LL long long
#define N (100005)
using namespace std;
int T,stx,sty,maxdep;
bool flag;
const int goal[6][6]={
    {0,0,0,0,0,0},
    {0,1,1,1,1,1},
    {0,0,1,1,1,1},
    {0,0,0,2,1,1},
    {0,0,0,0,0,1},
    {0,0,0,0,0,0},
};
const int dx[10]={-2,-1,1,2,2,1,-1,-2};
const int dy[10]={1,2,2,1,-1,-2,-2,-1};
int a[6][6];
inline int calc(){
    int ret=0;
    for (int i=1;i<=5;i++){
        for (int j=1;j<=5;j++) ret+=(goal[i][j]!=a[i][j]);
    }
    return ret;
}
inline bool safe(int x,int y){
    return x>=1&&x<=5&&y>=1&&y<=5;
} 
char c[10];
inline void IDAx(int u,int x,int y){
    if (u>maxdep){
        if (!calc()) flag=1;
        return;
    }
    for (int i=0;i<=7;i++){
        if (flag) return;
        if (safe(x+dx[i],y+dy[i])){
            swap(a[x][y],a[x+dx[i]][y+dy[i]]);
            x=x+dx[i],y=y+dy[i];
            if (calc()+u-1<=maxdep) IDAx(u+1,x,y);
            x-=dx[i],y-=dy[i];
            swap(a[x][y],a[x+dx[i]][y+dy[i]]);
        }
    }
}
template <typename T> void read(T&t) {
    t=0;
    bool fl=true;
    char p=getchar();
    while (!isdigit(p)) {
        if (p=='-') fl=false;
        p=getchar();
    }
    do {
        (t*=10)+=p-48;p=getchar();
    }while (isdigit(p));
    if (!fl) t=-t;
}
int main(){
    read(T);
    while (T--){
        for (int i=1;i<=5;i++){
            scanf("%s",c+1);
            for (int j=1;j<=5;j++){
                if (c[j]=='*'){
                    stx=i,sty=j;
                    a[i][j]=2;
                }
                else a[i][j]=c[j]-'0';
            }
        }
        flag=0;
        for (maxdep=1;maxdep<=15;maxdep++){
            IDAx(1,stx,sty);
            if (flag){
                printf("%d\n",maxdep);
                break;
            }
        }
        if (!flag) puts("-1"); 
    }
    return 0;
}