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
Daily Recommendation