第一眼看到就可以枚举空白格子位置然后跑bfs,处理一些细节就可以,这样的话最优能30分。

为了让程序跑的更快,我们可以在读入队列某个元素时记录其和目标状态对应位置不同的数量,因为交换一下最多能消去两个格子(第一次),其他情况最多能消去一个格子,所以当前的步数+数量>16或者当前步数>=15(这里可以为等于因为在其前面已经有循环保证如果步数为15就输出结果并return)。这样还有一个点TLE。那么我们可以在结构体里记录从上一个状态转移到当前状态的方向,这次要扩展的方向与上一个状态转移过来的方向相反,就说明跑回去了,然后就不要这个状态了。这样就能通过了
#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; }
 

技术
©2019-2020 Toolsou All rights reserved,
详解ubuntu14.04如何设置静态IPQCustomPlot系列(5)-实时动态曲线比尔·盖茨:疫情后彻底恢复正常可能要到2022年末华为认证HCIA-AI人工智能Python基础知识整理笔记百度、阿里、腾讯内部岗位级别和薪资结构,附带求职建议!Jsp+Ajax+Servlet+Mysql实现增删改查(一)2021年1月程序员工资统计,平均14915元Faster RCNN系列算法原理讲解(笔记)经典算法-递归(生兔子案例)