题目#

题解#

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

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

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

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

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

代码#

1
// luogu-judger-enable-o2
2
#include<bits/stdc++.h>
3
using namespace std;
4
const int n = 5;
5
string final = "111110111100*110000100000";
6
int dx[] = {1, 1, 2, 2, -2, -2, -1, -1};
7
int dy[] = {2, -2, 1, -1, 1, -1, 2, -2};
8
int dif(string s){
9
    int res = 0;
10
    for(int i = 0; i < n*n; ++i){
11
        if(s[i] != final[i])  res++;
12
    }
13
    return res;
14
}
15
string s;
16
int lim;
17
bool suc = 0;
18
void dfs(int cur, int last){
19
    if(cur == lim){    //是否搜索成功
20
        if(dif(s) == 0){
21
            suc = 1;
22
        }
23
        return;
24
    }
25
    if(suc)  return;    //最优解剪枝
26
    if(cur + max(0, dif(s) - 1) > lim)  return;    //当前值 + 最优值 > 迭代深度
27
    int f = s.find('*');
28
    int x = f/n, y = f%n;
29
    int xx, yy;
30
    for(int i = 0; i < 8; ++i){
31
        if(i + last == 7)  continue;    //防止回头，优化了很多
32
        xx = x + dx[i];
33
        yy = y + dy[i];
34
        if(xx >= 0 && xx < n && yy >= 0 && yy < n){
35
            swap(s[xx*n + yy], s[x*n + y]);
36
            dfs(cur+1, i);
37
            swap(s[xx*n + yy], s[x*n + y]);    //回溯
38
        }
39
    }
40
}
41
int main(){
42
    int T;
43
    cin >> T;
44
    while(T--){
45
        s = "";
46
        string tmp;
47
        for(int i = 1; i <= n; ++i){
48
            cin >> tmp;
49
            s += tmp;
50
        }
51
        if(dif(s) == 0)  cout << 0 << endl;
52
        else{
53
            suc = 0;
54
            for(int i = 1; i <= 15; ++i){
55
                lim = i;
56
                dfs(0, 9);
57
                if(suc){
58
                    cout << i << endl;
59
                    break;
60
                }
61
            }
62
            if(!suc)  cout << -1 << endl;
63
        }
64
    }
65
    return 0;
66
}