@[jayket](/user/1128556) BFS貌似会爆空间，要用迭代加深（$IDA*$）
by Humour_Fz @ 2023-12-22 18:32:51
@[jayket](/user/1128556) 参考一下我的代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
const int dx[8]={1,-1,1,-1,2,-2,2,-2},dy[8]={2,2,-2,-2,1,1,-1,-1};
const char mb[5][5]={
'1','1','1','1','1',
'0','1','1','1','1',
'0','0','*','1','1',
'0','0','0','0','1',
'0','0','0','0','0'
};
int t,fx,fy;char ma[5][5];bool f;
bool pd(){
for(int i=0;i<5;i++)for(int j=0;j<5;j++)if(ma[i][j]!=mb[i][j])return 0;
return 1;
}int g(){
int res=0;
for(int i=0;i<5;i++)for(int j=0;j<5;j++)if(ma[i][j]!=mb[i][j])res++;
return res;
}void dfs(int x,int y,int st,int ms){
if(x<0||y<0||x>4||y>4)return;
if(st>ms)return;
if(pd())return f=1,void();
for(int i=0;i<8;i++){
int tx=x+dx[i],ty=y+dy[i];
swap(ma[x][y],ma[tx][ty]);
if(g()+st<=ms)dfs(tx,ty,st+1,ms);
swap(ma[x][y],ma[tx][ty]);
}
}int main(){
cin>>t;
while(t--){
f=0;
for(int i=0;i<5;i++)for(int j=0;j<5;j++)cin>>ma[i][j],ma[i][j]=='*'&&(fx=i,fy=j);
for(int i=1;i<=15;i++){
dfs(fx,fy,0,i);
if(f){cout<<i<<'\n';break;}
}if(!f)cout<<-1<<'\n';
}
return 0;
}
```
by Humour_Fz @ 2023-12-22 18:33:31
@[XZH114514](/user/1056908)
没有爆空间，一开始爆了，但是改了一下就可以过了，然后就是有一个点的时间耗了很多，#9一开始跑了700+ms，然后我加了个特判剪枝就140ms左右了，但是还是WA了两个点
by jayket @ 2023-12-22 18:42:26
@[XZH114514](/user/1056908) 迭代加深还没怎么学，但是这个确实很简短
by jayket @ 2023-12-22 18:43:33