---

騎士精神(SCOI2005)

Description

在一個5×5的棋盤上有12個白色的騎士和12個黑色的騎士， 且有一個空位。在任何時候一個騎士都能按照騎 士的走法（它可以走到和它橫坐標相差為1，縱坐標相差為2或者橫坐標相差為2，縱坐標相差為1的格子）移動到空 位上。

給定一個初始的棋盤，怎樣才能經過移動變成如下目標棋盤：

為了體現出騎士精神，他們必須以最少的步 數完成任務。

Input Format

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

Output Format

對于每組數據都輸出一行。如果能在15步以內（包括15步）到達目標狀態，則輸出步數，否則輸出－1。

Sample Input

2 10110 01*11 10111 01001 00000 01011 110*1 01110 01010 00100

Sample Output

7 -1

解析

騎士的移動方式就是中國象棋中馬的移動方式，可以使用方位數組處理，我們不難到這樣一個簡單的\(dfs\)算法:搜索嘗試對每一頭馬進行合法的移動，并直接對目標狀態進行匹配。

由于馬的數量較多，顯然有很多移動是不合法的。每一次合法的移動只可能與唯一的空格交換位置，所以我們改變搜索策略，枚舉空格的移動。

題目中明顯給出了步數不大于十五的限制，所以我們不妨使用迭代加深的\(dfs\)算法。但是本題使用該算法仍然會超時，我們需要改進為\(IDA^*\)算法，可以如下簡單地設置估價函數:
\[f(s)=\sum_{s_{i,j}\ !=goal_{i,j}}1\]
即:當前狀態與目標狀態存在差異的位置個數，可以保證實際步數大于等于預估步數。

\(Code:\)

#include<bits/stdc++.h> using namespace std; #define mset(name,val) memset(name,val,sizeof name) #define filein(str) freopen(str".in","r",stdin) #define fileout(str) freopen(str".out","w",stdout) const int T=15,INF=0x3f3f3f3f; const int dx[]={1,-1,2,-2,1,-1,2,-2},dy[]={2,2,1,1,-2,-2,-1,-1}; const int goal[7][7]= {{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} }; int Map[10][10],beginx,beginy,ans=INF,Maxdep; inline void input(void) {for(int i=1;i<=5;i++){for(int j=1;j<=5;j++){char c=' ';while(isspace(c))c=getchar();if(c=='*')Map[i][j]=2,beginx=i,beginy=j;else Map[i][j]=c-'0';}} } inline int fspend(void) {int res=0;for(int i=1;i<=5;i++)for(int j=1;j<=5;j++)if(Map[i][j]!=goal[i][j])res++;return res; } inline bool dfs(int x,int y,int dep) {if(dep==Maxdep){if(!fspend())ans=dep;return true;}for(int i=0;i<8;i++){int tx=x+dx[i],ty=y+dy[i];if(tx<1||ty<1||tx>5||ty>5)continue;swap(Map[x][y],Map[tx][ty]);if(fspend()+dep<=Maxdep)if(dfs(tx,ty,dep+1))return true; swap(Map[tx][ty],Map[x][y]);}return false; } int main(void) {int T;scanf("%d",&T);while(T--){input();ans=0;for(Maxdep=1;Maxdep<=15;Maxdep++){if(dfs(beginx,beginy,0)){printf("%d\n",ans);break;}}if(!ans)printf("-1\n");}return 0; }

---

轉載于:https://www.cnblogs.com/Parsnip/p/10610681.html

總結

以上是生活随笔為你收集整理的『骑士精神 IDA*』的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。