本文主要是介绍P2324 [SCOI2005] 骑士精神，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
*原题链接*
T组测试数据，每组数据给定5x5的矩阵，求将其变为目标矩阵的最小步数。
做法：IDA*
分析：看到这样的数据范围和题目描述就可以想到搜索了，由于任何时候矩阵中只有一个空格，所以我们从空格开始进行搜索，看哪个骑士能转移到这个空格上。由于步数超过15步后输出-1，所以可以迭代加深搜索，但是这样爆搜后交上去会T，所以考虑如何优化。剪枝是剪不了的(至少我没想到哪里可以剪枝)，既然已经是迭代加深搜索了，那再考虑一下估价函数，变为IDA*，就能得到很大优化了，而估价函数也不难想，如果我们每次移动都能使一个骑士移到目标格子，那样的花费显然是最少的(具体见代码)。
#include<bits/stdc++.h>
using namespace std;
const int N=10;int T,mp[N][N],st,en,maxdeep,flag;
int dx[]={2,2,-2,-2,1,1,-1,-1};
int dy[]={1,-1,1,-1,2,-2,2,-2};
int goal[N][N]={{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 evaluate(){//估价函数，每次移动都能把不在目标格子上的骑士移到目标格子，花费是最少的int cnt=0;for(int i=1;i<=5;i++)for(int j=1;j<=5;j++)if(mp[i][j]!=goal[i][j]) cnt++;return cnt;
}void dfs(int x,int y,int dep){//IDA*if(dep==maxdeep){if(!evaluate()) flag=1;return;}for(int i=0;i<8;i++){int nx=x+dx[i],ny=y+dy[i];if(nx<1||ny<1||nx>5||ny>5) continue;swap(mp[x][y],mp[nx][ny]);int eva=evaluate();if(eva+dep<=maxdeep) dfs(nx,ny,dep+1);swap(mp[x][y],mp[nx][ny]);}
}int main(){ios::sync_with_stdio(false);cin>>T;while(T--){flag=0;for(int i=1;i<=5;i++){for(int j=1;j<=5;j++){char ch;cin>>ch;if(ch=='*') mp[i][j]=2,st=i,en=j;else mp[i][j]=ch-'0';}}for(maxdeep=0;maxdeep<=15;maxdeep++){dfs(st,en,0);if(flag){cout<<maxdeep<<endl;break;}}if(!flag) cout<<-1<<endl;}return 0;
}这篇关于P2324 [SCOI2005] 骑士精神的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
