P2324 骑士精神

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

A∗ 的核心思想是一个公式：
f(n)=g(n)+h(n)
f(n)是代价估值， g(n)是预计估值， h(n)是实际耗费
例如本题，如果你己经动了s步，还有g个骑士未归位，那么如果 s+g>15就可以直接剪枝，因为即使方案可行也不对答案产生任何贡献
显然 g(n)的好坏直接关乎算法的好坏，一般来讲， g(n)比最优解大，那么它就是错误的，没有任何意义； g(n)与最优解相同，此时是理想状态；如果 g(n)比最优解小，那么相差越大性能越差，而我们要尽可能的让 g(n)接近最优解，并严格不能超过最优解Code:
#include
#include
#include
#include
#include
#include
#include
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;
}

转载于:https://www.cnblogs.com/ukcxrtjr/p/11318761.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！