BZOJ 1085 [SCOI2005] 骑士精神

发布于 2017-07-02  152 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1085

题意:一个 5*5 的棋盘上有 12 个黑马,12 个白马和一个空位,给定一个目标状态,问 15 步以内能不能走到...


曾经吉大 WC 上一点都不会做的题也变成水题了...

直接深搜显然 T 死... 考虑 A*,如何构造估价函数呢?

显然除了最后一步以外每一步最多让一个棋子归位,那么可以用当前状态和目标状态不一致的格子数估价辣....

 


一个非常弱的准退役OIER