题目描述
输入输出格式
输入格式：
第一行有一个正整数T(T<=10)，表示一共有N组数据。接下来有T个5×5的矩阵，0表示白色骑士，1表示黑色骑士，*表示空位。两组数据之间没有空行。
输出格式：
对于每组数据都输出一行。如果能在15步以内（包括15步）到达目标状态，则输出步数，否则输出－1。
输入输出样例
输入样例#1：
2
10110
01*11
10111
01001
00000
01011
110*1
01110
01010
00100
输出样例#1：
7
-1
Solution：
又是变量名打错，调了有一会儿～滑稽～！
本题直接切入点是步数不超过$15$，很自然想到迭代加深搜索。
那么直接限制深度搜，一个可行性剪枝就是统计一下当前没有被还原的棋子个数，若大于步数则直接剪掉。
（瞎几把乱搞一通就好了，关键注意判重，不能回到上一个点，否则卡死循环。）
代码：
#include<bits/stdc++.h>
#define il inline
#define For(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
using namespace std;
int T,ans,stx,sty,w[][],ed[][]={
,,,,,,
,,,,,,
,,,,,,
,,,-,,,
,,,,,,
,,,,,
};
char s;
int dx[]={,,-,-,,,-,-},dy[]={,-,,-,,-,,-};
bool f;
il void dfs(int x,int y,int t,int lstx,int lsty){
if(!t)return;
int tot=;
For(i,,) For(j,,)
if(w[i][j]!=ed[i][j])tot++;
if(!tot){f=;return;}
if((tot>>)>t)return;
For(i,,){
int xx=dx[i]+x,yy=dy[i]+y;
if(xx>&&xx<&&yy>&&yy<&&(xx!=lstx|yy!=lsty)){
swap(w[xx][yy],w[x][y]),dfs(xx,yy,t-,x,y),swap(w[xx][yy],w[x][y]);
}
}
}
il bool solve(){
f=;
For(t,,){
dfs(stx,sty,t,,);
if(f){ans=t;return ;}
}
return ;
}
int main(){
ios::sync_with_stdio();
cin>>T;
while(T--){
For(i,,) For(j,,){
cin>>s;
if(s=='')w[i][j]=;
if(s=='*')w[i][j]=-,stx=i,sty=j;
if(s=='')w[i][j]=;
}
if(solve())cout<<ans-<<'\n';
else cout<<-<<'\n';
}
return ;
}