题目分析

题意：给你一个5x5的棋盘，按照“马走日”的方式移动棋子，用最少的步骤把输入的棋盘恢复成原样

解法一： IDA*
可以发现，每次枚举棋子的移动很难搜索
通过观察，因为每次马都只能移动到空格上面，那么问题就可以等价成移动空格使棋盘恢复原样

接下来设计估价函数f()
每次移动最多能让一个棋子归位
所以估价函数设计为：当前局面（除了空格）还有多少个棋子未归位

接下来就是常规的IDA*做法了

时间复杂度 O(8^15)

15步有解，每步拓展八个方向
因为会及时剪枝，时间复杂度远小于8^15

C++ 代码

#include<bits/stdc++.h>
using namespace std;
//黑-1白1k空0
int n;
int b[5][5]= {-1,-1,-1,-1,-1,
              1,-1,-1,-1,-1,
              1,1,0,-1,-1,
              1,1,1,1,-1,
              1,1,1,1,1
             };
int a[5][5];
int dx[]={1,-1,-1,1,2,-2,-2,2},dy[]={2,-2,2,-2,1,-1,1,-1};

int f()
{
    int res=0;
    for(int i=0; i<5; i++)
            for(int j=0; j<5; j++)
                if(a[i][j]&&a[i][j]!=b[i][j])
                    res++;
    return res;
}

bool dfs(int d,int x,int y,int depth)
{
    int val=f();
    if(!val){

        return true;
    }
    if(d+val>depth)
        return false;

    for(int i=0;i<8;i++)
    {
        int tx=x+dx[i],ty=y+dy[i];
        if(tx<0||tx>=5||ty<0||ty>=5)continue;

        swap(a[x][y],a[tx][ty]);
        if(dfs(d+1,tx,ty,depth))
            return true;
        swap(a[x][y],a[tx][ty]);
    }
    return false;
}
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        int x,y;
        for(int i=0; i<5; i++)
            for(int j=0; j<5; j++)
            {
                char c;
                cin>>c;
                if(c=='0')
                    a[i][j]=1;
                else if(c=='1')
                    a[i][j]=-1;
                else
                    a[i][j]=0,x=i,y=j;
            }

        bool flag=1;
        for(int depth=0;depth<=15; depth++)
        {
            if(dfs(0,x,y,depth))
            {
                cout<<depth<<endl;
                flag=0;
                break;
            }
        }
        if(flag)
            cout<<-1<<endl;
    }
    return 0;
}

解法二： 双向BFS $O(8 ^ 7)$

双向$BFS$的实现有多种：

1. 把初始状态和目标状态扔在一个队列里，每次从队列里搞出来一个扩展
2. 把初始状态和目标状态扔在两个队列里，每次选一个队列中元素少的拓展。
3. 把初始状态和目标状态扔在两个队列里，每次分别从两个队列中取出一个元素拓展。

这里使用了方法$1$。

时间复杂度分析：每次会扩展$8$个状态，最多扩展$\lfloor\frac{15}{2}\rfloor = 7$次（到第八次如果还找不到则肯定超过限制的$15$步，答案则无需扩展），所以复杂度是$O(8 ^ 7)$的

具体实现方面看代码。

C++ 代码

#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int INF = 0x3f3f3f3f;
int dx[8] = {1, 1, -1, -1, 2, 2, -2, -2};
int dy[8] = {-2, 2, 2, -2, 1, -1, 1, -1};
//移动方向的打表
int n;
//状态结构体
struct Node{
    int v[5][5], f, x, y;
    //f = 0 表示从初始状态出发， f = 1 表示从目标状态出发
}s, t, u;
unordered_map<int, int> step[2][30];
// 记录每个状态对应的位置。
int goal[5][5] = {
    {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 start[5][5];

//get(x) 获取状态x的步数
int get(Node x){
    int  sum = 0;
    //把一个位置状态转移成一个二进制数，比较方便。
    for(int i = 0; i < 5; i++)
        for(int j = 0; j < 5; j++)
            if(x.v[i][j] == 1)
                sum |= 1 << (i * 5 + j);
    if(step[x.f][x.x * 5 + x.y].count(sum) == 0) return INF;
    return step[x.f][x.x * 5 + x.y][sum];
}
//set() 设置状态x的步数
void set(Node x, int val){
    int sum = 0;
    for(int i = 0; i < 5; i++)
        for(int j = 0; j < 5; j++)
            if(x.v[i][j] == 1)
                sum |= 1 << (i * 5 + j);
    step[x.f][x.x * 5 + x.y][sum] = val;
}
int bfs(){
    queue<Node> q;
    q.push(s); q.push(t);
    set(s, 0);
    set(t, 0);
    while(!q.empty()){
        Node u = q.front(); q.pop();



        //找到同位置的另一状态
        Node l = u; l.f = u.f ^ 1;

        //如果相遇，代表已经找到一条最短的路径
        if(get(u) + get(l) <= 15)
            return get(u) + get(l);

        //说明所有状态已经都至少走了 8 步， > 最大限制 15
        if(get(u) >= 8) break;

        l.f = u.f;
        for(int i = 0; i < 8; i++){
            int nx = u.x + dx[i], ny = u.y + dy[i];
            if(nx < 0 || nx >= 5 || ny < 0 || ny >= 5) continue;
            swap(l.v[u.x][u.y], l.v[nx][ny]);
            l.x = nx, l.y = ny;

            if(get(u) + 1 < get(l)){
                set(l, get(u) + 1);
                q.push(l);
            }
            //还原现场
            swap(l.v[u.x][u.y], l.v[nx][ny]);
        }
    }
    return -1;
}
int main(){
    for(int i = 0; i < 5; i++)
        for(int j = 0; j < 5; j++)
            t.v[i][j] = goal[i][j];
    t.f = 1; t.x = 2; t.y = 2;
    int T; scanf("%d", &T);
    while(T--){
        for(int i = 0; i < 2; i++)
            for(int j = 0; j < 30; j++)
                step[i][j].clear();
        for(int i = 0; i < 5; i++){
            for(int j = 0; j < 5; j++){
                char x; cin >> x;
                if(x == '*')s.x = i, s.y = j, s.v[i][j] = 2;
                else s.v[i][j] = x - '0';
            }
        }
        s.f = 0;
        printf("%d\n", bfs());
    }
    return 0;
}