[luoguP2324] [SCOI2005]骑士精神（A*？）

传送门

蒟蒻并不懂A*是什么，但是题解里有个Astar

可以看出，当前棋盘和最终的棋盘如果有k个不同的，那么至少需要k1步来移动

所以如果 当前步数 + k 1 > limit 就直接退出

然后当然就是用喜闻乐见的迭代加深搜索啦，广搜占空间那么大又难写

最后吐槽一句，为什么我加哈希判重反而比不判重慢。。？

#include <cstdio>#define swap(x, y) ((x) ^= (y) ^= (x) ^= (y)) #define P 1000007int T, limit;char s[6][6], t[6][6];int dx[8] = ,dy[8] = ;bool vis[P];inline bool dfs(int k)if(!cnt) return 1;cnt;if(k > limit) return 0;if(vis[hash]) return 0;if(k + cnt  1 > limit) return 0;for(i = 0; i < 8; i++)}return 0;}int main()limit++;}if(limit > 15) puts("1");}return 0;}

上一篇：[luoguP2518][HAOI2010]计数（数位DP）

下一篇：[luoguP2053] [SCOI2007]修车（最小费用最大流）