第一次寫A*暴搜啊，感覺(jué)好爽，搜一搜就出來(lái)了（其實(shí)是照著別人寫的23333），詳細(xì)見(jiàn)代碼.
#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()//判斷與最終態(tài)是否相同 { 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)//估價(jià)函數(shù) { 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){新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
