(mathcal{color{red}{Description}})
嗯，(15)步之内走不到就输出(-1).
(mathcal{color{red}{Solution1}})
这个题是我第一次写迭代加深ORZ…没想到并不简单啊。
首先我们考虑如果移动每个不在原位子上的棋子，好像根本不可做，状态之间的关系错综复杂，所以我么考虑移动空格。
那么，我们如何来定义每一步的状态呢？我们对于搜索的每一步，记录状态(sum)为“还剩下多少未归位的棋子”，然后迭代加深的层数便是最开始有多少未归位的棋子数~16。这个(16)显然是由步数上限(15)得来的，(+1)的原因是因为我的(code)是在第(n)层搜索之前判断是否到达规定的搜索深度(k)。
嗯，接着就要分下面几种情况来讨论：
对于下一层状态(sum)而言（），设现在空格的位置为(A(x, y))，跳一步之后到达的位置是(A'(kx, ky))，那么这次操作就等价于(A)和(A‘)位置的互换。
1、如果换位之前，(A’)和正确的矩阵中(A')的颜色一致，但是(A)的颜色和正确矩阵中的(A’)位置颜色也相同，那换了和没换没有区别，所以并不考虑这一点。
2、如果换位之前，(A’)和正确的矩阵中(A')的颜色一致，但是(A)的颜色和正确矩阵中的(A’)位置颜色不相同，那换了之后未归位数就会变多，所以(sum ++)。
if (now[kx][ky] == rht[kx][ky] && now[kx][ky] != rht[x][y]) sum ++ ;
3、如果换位之前，(A’)和正确的矩阵中(A')的颜色不一致，但是(A)的颜色和正确矩阵中的(A’)位置颜色相同，那换了之后未归位数就会变少，所以(sum --)。
if (now[kx][ky] != rht[kx][ky] && now[kx][ky] == rht[x][y]) sum -- ;
4、如果下一步走到了空格上，那么说明有空格归位了，$sum -- $
if (rht[kx][ky] == -1) sum -- ;
5、如果这一步走到了空格，那么下一步就势必要多一个未归位的，所以(sum ++)
if (rht[x][y] == -1) sum ++ ;
嗯，唐子川大佬给我讲的qwq。
那么看起来好像比(5 imes 5)的枚举快多了，但我并不知道到何时我才会有这种素养让我能想出这种剪枝(QAQ).
// luogu-judger-enable-o2
//Flower学习专用
#include<cstdio>
#include<iostream>
#define rep(i, a, b) for(int i = a; i <= b; i ++)
using namespace std ;
bool mark = 0;
char k ;
int mp = 0, max_deep, T, stx, sty, i, kk;
int fx[8]={-2,-2,-1,1,-1,1,2,2},
fy[8]={-1,1,2, 2,-2,-2,-1,1};
int now[6][6], rht[6][6] = { {},
{0, 1, 1, 1, 1, 1},
{0, 0, 1, 1, 1, 1},
{0, 0, 0, -1, 1, 1},
{0, 0, 0, 0, 0, 1},
{0, 0, 0, 0, 0, 0},
};
bool knight(int step, int left, int last, int x, int y){
if (step + left > max_deep) return 0;
if (!left) return 1 ;
int kx, ky;
int j ;
rep (j, 0, 7){
if (j == 7 - last) continue ;
kx = x + fx[j] ;
ky = y + fy[j] ;
int lleft = left ;
if(kx < 1 || ky < 1 || kx > 5 || ky > 5) continue ;
if (now[kx][ky] == rht[kx][ky] && now[kx][ky] != rht[x][y]) lleft ++ ;
if (now[kx][ky] != rht[kx][ky] && now[kx][ky] == rht[x][y]) lleft -- ;
if (rht[kx][ky] == -1) lleft -- ;
if (rht[x][y] == -1) lleft ++ ;
swap(now[kx][ky], now[x][y]) ;
if (knight(step + 1, lleft, j, kx, ky)) return 1 ;
swap(now[kx][ky], now[x][y]) ;
}
return 0 ;
}
int main(){
cin >> T ;
while(T --){
mp = 0 ;
mark = 0 ;
rep(i, 1, 5)
rep(kk, 1, 5){
cin >> k ;
if (k == '*') {
now[i][kk] = -1 ;
stx = i ;
sty = kk ;
}
else now[i][kk] = k - 48;
if(now[i][kk] != rht[i][kk]) mp ++ ;
}
rep(i, mp, 16){
max_deep = i ;
if (knight(0, mp, -1, stx, sty)){
cout << i - 1 << endl;
mark = 1 ;
break ;
}
}
if(!mark) cout << -1 << endl ;
}
}