At first sight, you can enumerate the blank grid positions and run bfs, Just deal with the details , In this way, the optimal energy 30 branch .

In order to make the program run faster , We can record the number of different positions corresponding to the target state when reading an element in the queue , Because you can eliminate up to two squares in exchange ( for the first time ), In other cases, at most one grid can be eliminated , So the current steps + number >16 Or current steps >=15( This can be equal to because there is a cycle guarantee before it if the number of steps is 15 Just output the results and return). There's another point TLE. Then we can record the direction from the previous state to the current state in the structure , This time, the expansion direction is opposite to the direction of the previous state , It's like running back , And then we don't want that . So we can get through
#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib>
#include<algorithm> using namespace std; const int maxn=2000100; const int
dx[8]={1,2,2,1,-1,-2,-2,-1}; const int dy[8]={2,1,-1,-2,2,1,-1,-2}; struct H {
char map[6][6]; int step; int x; int y; int last; }team[maxn]; int tot; char
bz[6][6]= {{'0','0','0','0','0','0'}, {'0','1','1','1','1','1'},
{'0','0','1','1','1','1'}, {'0','0','0','*','1','1'},
{'0','0','0','0','0','1'}, {'0','0','0','0','0','0'}}; void bfs() { int
s=1,t=1; t++; while(s!=t) { H now=team[s]; s++; s%=maxn; int k=0; // cout<<s<<'
'<<t<<' '<<now.step<<' '<<now.x<<' '<<now.y<<endl; // for(int i=1;i<=5;i++) //
{ // for(int j=1;j<=5;j++) // { // cout<<now.map[i][j]; // } // cout<<endl; //
} for(int i=1;i<=5;i++) { for(int j=1;j<=5;j++) { if(now.map[i][j]!=bz[i][j]) {
k++; } } } if(k==0) { printf("%d\n",now.step); return ; } else
if(now.step+k>16||now.step>=15) { continue; } for(int q=0;q<8;q++) {
if(q==7-now.last) continue; int xx=dx[q]+now.x; int yy=dy[q]+now.y;
if(xx>=1&&xx<=5&&yy>=1&&yy<=5) { team[t].x=xx; team[t].y=yy;
swap(now.map[xx][yy],now.map[now.x][now.y]); for(int i=1;i<=5;i++) { for(int
j=1;j<=5;j++) { team[t].map[i][j]=now.map[i][j]; } } team[t].step=now.step+1;
team[t].last=q; t++; t%=maxn; swap(now.map[xx][yy],now.map[now.x][now.y]); } }
} cout<<"-1"<<endl; } int main() { scanf("%d",&tot); while(tot--) {
memset(team,0,sizeof(team)); for(int i=1;i<=5;i++) { for(int j=1;j<=5;j++) {
char c; c=getchar(); while(c=='\n'||c==' '||c=='\r') c=getchar();
team[1].map[i][j]=c; if(c=='*') { team[1].x=i; team[1].y=j; } } }
team[1].step=0; team[1].last=-1; bfs(); } return 0; }
 

Technology
©2019-2020 Toolsou All rights reserved,
Python Basic knowledge and notes 2021 year 1 Monthly programmer salary statistics , average 14915 element GDOI2019 travels C++ Standard library What should I do if I suddenly encounter a question I can't answer during the interview ?2021 year 2 Monthly programmer salary statistics , average 15144 element college examination for the self-taught An overview of Marxism use C++ I want to talk to you “ Prototype mode ” ( copy / copy constructor ) How to use it quickly html and css Write static page Bitcoin in ten years ,VDS Opportunity or fraud