Description
在一個(gè)5×5的棋盤(pán)上有12個(gè)白色的騎士和12個(gè)黑色的騎士， 且有一個(gè)空位。在任何時(shí)候一個(gè)騎士都能按照騎士的走法（它可以走到和它橫坐標(biāo)相差為1，縱坐標(biāo)相差為2或者橫坐標(biāo)相差為2，縱坐標(biāo)相差為1的格子）移動(dòng)到空位上。 給定一個(gè)初始的棋盤(pán)，怎樣才能經(jīng)過(guò)移動(dòng)變成如下目標(biāo)棋盤(pán)： 為了體現(xiàn)出騎士精神，他們必須以最少的步數(shù)完成任務(wù)。

Input
第一行有一個(gè)正整數(shù)T(T<=10)，表示一共有N組數(shù)據(jù)。接下來(lái)有T個(gè)5×5的矩陣，0表示白色騎士，1表示黑色騎士，*表示空位。兩組數(shù)據(jù)之間沒(méi)有空行。

Output
對(duì)于每組數(shù)據(jù)都輸出一行。如果能在15步以?xún)?nèi)（包括15步）到達(dá)目標(biāo)狀態(tài)，則輸出步數(shù)，否則輸出－1。

Sample Input
2
10110
01*11
10111
01001
00000
01011
110*1
01110
01010
00100
Sample Output
7
-1

A*：
s為當(dāng)前深度，u為與目標(biāo)不一樣的數(shù)量，枚舉ans，如果s+u>ans就不用搜了

code：

//By Menteur_Hxy #include <cstdio> #include <iostream> #include <cstring> #define f(i,a,b) for(register int i=(a);i<=(b);i++) using namespace std;int T,k,x,y,flag=0; int da[5][5]; int aim[5][5]={{1,1,1,1,1},{0,1,1,1,1},{0,0,2,1,1},{0,0,0,0,1},{0,0,0,0,0} }; int xx[8]={1,1,-1,-1,2,2,-2,-2}; int yy[8]={2,-2,2,-2,1,-1,1,-1};bool jud(int a[5][5]) {f(i,0,4) f(j,0,4) if(a[i][j]!=aim[i][j]) return 0;return 1; }bool eva(int a[5][5],int s) {int u=0;f(i,0,4) f(j,0,4) if(a[i][j]!=aim[i][j]) if((++u)+s>k) return 0;return 1; }void serch(int s,int a[5][5],int x,int y) {if(s==k) {if(jud(a)) flag=1; return ;}if(flag) return ;f(i,0,8) {int nx=x+xx[i],ny=y+yy[i];if(nx<0 || nx>4 || ny<0 || ny>4) continue;swap(a[x][y],a[nx][ny]);if(eva(a,s)) serch(s+1,a,nx,ny);swap(a[x][y],a[nx][ny]);} }int main() {scanf("%d",&T);while(T--) {memset(da,0,sizeof da);f(i,0,4) { char ch[10]; scanf("%s",ch);f(j,0,4) if(ch[j]=='*') da[i][j]=2,x=i,y=j;else da[i][j]=ch[j]-'0';}for(k=1;k<=15;k++) {serch(0,da,x,y); if(flag) {printf("%d\n",k);break;}}if(!flag) printf("-1\n");else flag=0;}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/Menteur-Hxy/p/9247973.html

總結(jié)

以上是生活随笔為你收集整理的[luogu 2324][SCOI 2005] 骑士精神 (A*算法)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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