SCOI2005-骑士精神

题目

luoguP2324

题解

首先很容易想到的是，应该用空格去跳，而不是用马，因为马的数量太多了。

第二，因为搜索状态太多，考虑用使用IDDFS + A*，有一个比较简单的估价函数就是当前状态和终态的不同元素的个数。

考虑到折返是没有任何价值的，因此在搜索过程中保留上一次搜索的方向，在本次搜索中如果是折返操作则跳过。

未跳过折返时时间：1509ms，跳过后：66ms。

可以看出来优化还是很巨大的。

代码

// luogu-judger-enable-o2
#include<bits/stdc++.h>
using namespace std;
const int n = 5;
string final = "111110111100*110000100000";
int dx[] = {1, 1, 2, 2, -2, -2, -1, -1};
int dy[] = {2, -2, 1, -1, 1, -1, 2, -2};
int dif(string s){
    int res = 0;
    for(int i = 0; i < n*n; ++i){
        if(s[i] != final[i])	res++;
    }
    return res;
}
string s;
int lim;
bool suc = 0;
void dfs(int cur, int last){
    if(cur == lim){		//是否搜索成功
        if(dif(s) == 0){
            suc = 1;
        }
        return;
    }
    if(suc)	return;		//最优解剪枝
    if(cur + max(0, dif(s) - 1) > lim)	return;		//当前值 + 最优值 > 迭代深度	
    int f = s.find('*');
    int x = f/n, y = f%n;
    int xx, yy;
    for(int i = 0; i < 8; ++i){
        if(i + last == 7)	continue;		//防止回头，优化了很多
        xx = x + dx[i];
        yy = y + dy[i];
        if(xx >= 0 && xx < n && yy >= 0 && yy < n){
            swap(s[xx*n + yy], s[x*n + y]);
            dfs(cur+1, i);
            swap(s[xx*n + yy], s[x*n + y]);		//回溯
        }
    }
}
int main(){
    int T;
    cin >> T;
    while(T--){
        s = "";
        string tmp;
        for(int i = 1; i <= n; ++i){
            cin >> tmp;
            s += tmp;
        }
        if(dif(s) == 0)	cout << 0 << endl;
        else{
            suc = 0;
            for(int i = 1; i <= 15; ++i){
                lim = i;
                dfs(0, 9);
                if(suc){
                    cout << i << endl;
                    break;
                }
            }
            if(!suc)	cout << -1 << endl;
        }
    }
    return 0;
}