題面:https://www.luogu.org/problem/P2324

A? 的核心思想是一個(gè)公式： f(n)=g(n)+h(n) f(n)是代價(jià)估值， g(n)是預(yù)計(jì)估值， h(n)是實(shí)際耗費(fèi) 例如本題，如果你己經(jīng)動(dòng)了s步，還有g(shù)個(gè)騎士未歸位，那么如果 s+g>15就可以直接剪枝，因?yàn)榧词狗桨缚尚幸膊粚?duì)答案產(chǎn)生任何貢獻(xiàn) 顯然 g(n)的好壞直接關(guān)乎算法的好壞，一般來講， g(n)比最優(yōu)解大，那么它就是錯(cuò)誤的，沒有任何意義； g(n)與最優(yōu)解相同，此時(shí)是理想狀態(tài)；如果 g(n)比最優(yōu)解小，那么相差越大性能越差，而我們要盡可能的讓 g(n)接近最優(yōu)解，并嚴(yán)格不能超過最優(yōu)解Code: #include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<cstdlib> #include<algorithm> #include<ctime> using namespace std; const int d[6][6]={{0,0,0,0,0,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}}; const int dx[]={1,1,2,2,-1,-1,-2,-2}; const int dy[]={2,-2,1,-1,2,-2,1,-1}; int t,a[6][6],xa,ya; bool flag; int get_g(){int cnt=0;for(int i=1;i<=5;i++){for(int j=1;j<=5;j++){if(d[i][j]!=a[i][j]){++cnt;}}}return cnt; } void A_star(int x,int y,int f,int s){int g=get_g();if(g==0){flag=1;return;}if(s+g>f+1){return;}for(int i=0;i<8;i++){int xx=x+dx[i],yy=y+dy[i];if(xx<=0||xx>5||yy<=0||yy>5){continue;}swap(a[xx][yy],a[x][y]);A_star(xx,yy,f,s+1);swap(a[xx][yy],a[x][y]);} } int main(){scanf("%d",&t);while(t--){for(int i=1;i<=5;i++)for(int j=1;j<=5;j++){char c;cin>>c;if(c=='*'){xa=i,ya=j;a[i][j]=2;}else{a[i][j]=c-'0';}}for(int i=1;i<=15;i++){flag=0;A_star(xa,ya,i,0);if(flag){printf("%d\n",i);break;}}if(!flag){puts("-1");}}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/ukcxrtjr/p/11318761.html

總結(jié)

以上是生活随笔為你收集整理的P2324 骑士精神的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。