[luogu P2324] [SCOI2005]骑士精神
题目描述
输入输出格式
输入格式：
第一行有一个正整数T(T<=10)，表示一共有N组数据。接下来有T个5×5的矩阵，0表示白色骑士，1表示黑色骑士，*表示空位。两组数据之间没有空行。
输出格式：
对于每组数据都输出一行。如果能在15步以内（包括15步）到达目标状态，则输出步数，否则输出－1。
输入输出样例
输入样例#1：
2 10110 01*11 10111 01001 00000 01011 110*1 01110 01010 00100
输出样例#1：
7 -1
说明
看了一下ida*，发现真的比a*简单多了。。ida*无非就是设定一个预期步数，然后运用a*的思想，即——
如果当期实际步数+估计剩余步数>预期步数，则return。显然，估计剩余步数一定不超过实际剩余步数，否则会漏掉最优解。
对于这题来说，估计剩余步数可以采取错位数-1。
错位数即每一个位置上与目标不一致的数量，减一是因为可能在最后用1步能减掉2个错位数，毕竟估价函数越小，可能效率越低，但是至少错误率下降了，对与这题，错误率就为0了。
那什么题目适合ida*呢？当预期步数不大，但是每一层状态数很多时，就适合ida*，毕竟这时bfs已经不适用了。
code：
%:pragma GCC optimize()
#include<bits/stdc++.h>
#define swap(x,y) ((x)^=(y)^=(x)^=(y))
using namespace std;
][]={{,,,,},{,,,,},{,,,,},{,,,,},{,,,,}};
][]={{,},{,},{-,},{-,},{,-},{,-},{-,-},{-,-}};
][],ori[][],dis[][];
inline int get() {
;
; i<=n; i++)
; j<=n; j++)
ret+=(a[i][j]!=aim[i-][j-]);
return ret;
}
inline void idastar(int d,int x,int y) {
) return; int c=get();
) {rea=d; return;}
>s) return;
; i<; i++) {
],yy=y+fl[i][];
||xx>n||yy<||yy>n) continue;
swap(a[x][y],a[xx][yy]);
idastar(d+,xx,yy);
) return;
swap(a[x][y],a[xx][yy]);
}
}
int main() {
];
scanf(;
for (; T; T--) {
rea=;
; i<=n; i++) {
scanf();
; j<=n; j++)
ori[i][j]=(c[j]==:c[j]-;
}
; i<=n; i++)
; j<=; j++)
) {sx=i,sy=j; break;}
; s<=; s++) {
memcpy(a,ori,sizeof a);
idastar(,sx,sy);
) break;
}
) puts("-1"); else printf("%d\n",rea);
}
;
}