【题解】Luogu 2324 BZOJ 1085【骑士精神】

背景

这题启发式搜索可写死我了,最后居然发现是一个小小减号写成了等号,很烦。

分析

深搜严重超时,而且这里题目直接说了“多于$15$步不出解就输出$-1$”这种字样,就是提醒我们用启发式搜索,$A-Star$。
这里的估计函数很简单,就是统计有多少个马在它不该在的位置,然后判断步数就好了。

代码

#include<cstdio>
#include<string>
#include<iostream>
#include<algorithm>
#include<cstring>
using std::cin;using std::string;using std::swap;
const int MAXN = 5 + 6;
const int ANS[MAXN][MAXN] = 
{{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 dx[8]={1,1,-1,-1,2,2,-2,-2};
int dy[8]={2,-2,2,-2,1,-1,1,-1};
int map[MAXN][MAXN],x0,y0,k;
int running = 0;

int oysj(int s){
    int key = 0;
    for(int i = 0;i < 5;i++) 
        for(int j = 0;j < 5;j++) 
            if(map[i][j] != ANS[i][j]){key++;if(key + s > k) return 0;}
    return 1;
}

int equals(){
    for(int i = 0;i < 5;i++)
        for(int j = 0;j < 5;j++)
            if(ANS[i][j] != map[i][j]) return 0;
    return 1;
}

void AStar(int x,int y,int s){
    if(s == k){
        if(equals()) running = 1;
        return;
    }
    if(running == 1) return;
    for(int i = 0;i < 8;i++){
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(nx < 0 || ny < 0 || nx > 4 || ny > 4) continue;
        swap(map[nx][ny],map[x][y]);
        if(oysj(s)) AStar(nx,ny,s + 1);
        swap(map[nx][ny],map[x][y]);
    }
}

int main(){
    //freopen("in.txt","r",stdin);
    //freopen("out2.txt","w",stdout);
    int T;scanf("%d",&T);
    while(T--){
        memset(map,0,sizeof(map));
        string s[MAXN];
        for(int i = 0;i < 5;i++){
            cin >> s[i];
            for(int j = 0;j < 5;j++){
                if(s[i][j] == '*') map[i][j] = 2,x0 = i,y0 = j;
                else map[i][j] = s[i][j] - '0';
            }
        }
        for(k = 1;k <= 15;k++){
            AStar(x0,y0,0);

            if(running){
                printf("%d\n",k);
                break;
            }
        }
        if(!running) printf("-1\n");
        else running = false;
    }

    return 0;
}