[SCOI2005]骑士精神
描述
在一个\(5×5\)的棋盘上有\(12\)个白色的骑士和\(12\)个黑色的骑士， 且有一个空位。在任何时候一个骑士都能按照骑
士的走法（它可以走到和它横坐标相差为\(1\)，纵坐标相差为\(2\)或者横坐标相差为\(2\)，纵坐标相差为\(1\)的格子）移动到空 位上。 给定一个初始的棋盘，怎样才能经过移动变成如下目标棋盘： 为了体现出骑士精神，他们必须以最少的步 数完成任务。
输入
第一行有一个正整数\(T(T<=10)\)，表示一共有\(N\)组数据。接下来有\(T\)个\(5×5\)的矩阵，\(0\)表示白色骑士，\(1\)表示黑色骑 士，\(*\)表示空位。两组数据之间没有空行。
输出
对于每组数据都输出一行。如果能在\(15\)步以内（包括\(15\)步）到达目标状态，则输出步数，否则输出-\(1\)。
输入样例 1:
21011001*1110111010010000001011110*1011100101000100
输出样例1：
7-1
题解
题意：给你一个初始棋盘，要求用最少的步数移动马达到如上图的目标状态（要求棋盘中的马只能走“日”）。
咱们先抛开\(IDA^*\)，先如何优化爆搜；
这里的马和象棋里的马走法相同，但题目中要求让马走，但是要是马的话，搜索分支比较多，所以我们要考虑让空格走（很显然吧）。
下面步入正题：
\(IDA^*\)就是带有迭代加深和估价函数优化的搜索。
可能某些人对以上两个名词很陌生，下面一些前置知识可能会带你透彻一下。
前置知识1：迭代加深
定义：
每次限定一个\(maxdep\)最大深度，使搜索树的深度不超过\(maxdep\)。
for(R int maxdep=1;maxdep<=题目中给的最大步数;maxdep++){ dfs(0,maxdep);//0为出入函数中当前步数，maxdep为传入的最大深度。 if(success)break;//如果搜索成功则会在dfs函数中将success赋值为1。 } 使用范围:
1.在有一定的限制条件时使用（例如本题中“如果能在\(15\)步以内（包括\(15\)步）到达目标状态，则输出步数，否则输出\(－1\)。“）。
2.题目中说输出所以解中的任何一组解。
为什么能够降低时间复杂度：
我们可能会在一个没有解（或解很深的地方无限递归然而题目中要求输出任何的一组解），所以我们限制一个深度，让它去遍历更多的分支，去更广泛地求解，(其实和\(BFS\)有异曲同工之妙)。
前置知识2：估价函数
定义：
\(f(n)=g(n)+h(n)\)
其中\(f(n)\)是节点的估价函数，\(g(n)\)是现在的实际步数，\(h(n)\)是对未来步数的最完美估价（“完美”的意思是可能你现实不可能实现，但你还要拿最优的步数去把\(h(n)\)算出来，可能不太好口胡，可以参考下面的实例）。
应用：
void dfs(int dep,int maxdep){ if(evaluate()+dep>maxdep)return; //evaluate函数为对未来估价的函数，若未来估价加实际步数>迭代加深的深度则return。 if(!evaluate){ success=1; printf("%d\n",dep); return; } ...... } 前置知识3：\(A^*\)和\(IDA^*\)的区别
\(A^*\)是用于对\(BFS\)的优化；
\(IDA^*\)是对结合迭代加深的\(DFS\) 的优化。
本质上只是在\(BFS\)和\(DFS\)上加上了一个估价函数。
何时使用因题而定：
\(A^*\)（）;\(IDA^*\)（和 就是上面的两道题）。
前置知识毕！！！
现在就是要想一个比较好的估价函数（若估价函数不好的话，优化效率就并不高，例如若估价函数一直为0，那就是爆搜）。
我们可以想一下，每次空白格子和黑白棋子交换，最优的情况就是每次都把黑白棋子移动到目标格子。
那么你的估价函数就出来了：
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} }; inline int evaluate(){ R int cnt=0; for(R int i=1;i<=5;i++) for(R int j=1;j<=5;j++) if(mp[i][j]!=goal[i][j])cnt++; return cnt; } 下面就是爆搜了：
#include#include #include #include #include #define ll long long#define R registerusing namespace std;template inline void read(T &a){ char c=getchar();T x=0,f=1; while(!isdigit(c)){if(c=='-')f=-1;c=getchar();} while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();} a=f*x;}int n,m,t,mp[7][7],stx,sty,success;char ch;const int dx[]={0,1,1,-1,-1,2,2,-2,-2};const int dy[]={0,2,-2,2,-2,1,-1,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}};inline int evaluate(){ R int cnt=0; for(R int i=1;i<=5;i++) for(R int j=1;j<=5;j++) if(mp[i][j]!=goal[i][j])cnt++; return cnt;}inline int safe(R int x,R int y){ if(x<1||x>5||y<1||y>5)return 0; return 1;}inline void A_star(R int dep,R int x,R int y,R int maxdep){ if(dep==maxdep){ if(!evaluate())success=1; return; } for(R int i=1;i<=8;i++){ R int xx=x+dx[i]; R int yy=y+dy[i]; if(!safe(xx,yy))continue; swap(mp[x][y],mp[xx][yy]); int eva=evaluate(); if(eva+dep<=maxdep) A_star(dep+1,xx,yy,maxdep); swap(mp[x][y],mp[xx][yy]);//回溯 }}int main(){ read(t); while(t--){ success=0; for(R int i=1;i<=5;i++){ for(R int j=1;j<=5;j++){ cin>>ch; if(ch=='*')mp[i][j]=2,stx=i,sty=j;//记录起点即为空白格子 else mp[i][j]=ch-'0'; } } if(!evaluate()){printf("0\n");continue;} for(R int maxdep=1;maxdep<=15;maxdep++){ A_star(0,stx,sty,maxdep); if(success){printf("%d\n",maxdep);goto ZAGER;} } printf("-1\n"); ZAGER:; } return 0;}