第一次写A*暴搜啊，感觉好爽，搜一搜就出来了（其实是照着别人写的23333），详细见代码.
#include<iostream>#include<cstdio>#include<cstring>using namespace std;int end[6][6]={{0}, {0,1,1,1,1,1}, {0,0,1,1,1,1}, {0,0,0,2,1,1}, {0,0,0,0,0,1}, {0,0,0,0,0,0},};int sx[8]={1,1,-1,-1,2,2,-2,-2};int sy[8]={2,-2,2,-2,1,-1,1,-1};int T,now[6][6],k;int flag;char ch;inline int judge()//判断与最终态是否相同 { for (int i=1;i<=5;++i) for (int j=1;j<=5;++j) if (end[i][j]!=now[i][j])return false; return true;}inline int eva(int step)//估价函数 { int tot=0; for (int i=1;i<=5;++i) for (int j=1;j<=5;++j) if (now[i][j]!=end[i][j]) { ++tot; if (step+tot>k)return false; } return true;}inline void dfs(int step,int x,int y){ if (step==k&&judge()) { flag=true; return ; } if (flag)return ; for(int i=0;i<8;++i) { int nowx=x+sx[i],nowy=y+sy[i]; if (nowx>0&&nowx<=5&&nowy>0&&nowy<=5) { swap(now[x][y],now[nowx][nowy]); if (eva(step))dfs(step+1,nowx,nowy); swap(now[x][y],now[nowx][nowy]); } }}int main(){ int x,y; scanf("%d",&T); while(T--) { for (int i=1;i<=5;++i) for (int j=1;j<=5;++j) { ch=getchar(); while(ch!='1'&&ch!='0'&&ch!='*')ch=getchar(); if (ch=='*') { x=i,y=j; now[i][j]=2; } else now[i][j]=ch-'0'; } for (k=1;k<=15;++k) { flag=false; dfs(0,x,y); if (flag){ PRintf("%d/n",k); break; } } if (!flag)printf("-1/n"); }}新闻热点
疑难解答
