洛谷1979 - 华容道

一道经典的搜索题。由于棋子没必要也不可能和非空格的棋子交换,目标棋子也只可能通过与空格交换位置达到目标位置,因此我们只需要存储空格和目标棋子的位置即可。这样爆搜即可拿到 $80$ 分。

接着考虑能否继续优化:每次目标棋子改变位置空格必须在他旁边,因此存储除了初始状态和终止状态外的空格不在目标棋子旁边的状态没有意义。因此我们可以用 BFS 处理出状态之间转移的代价,然后用 SPFA 等最短路算法跑一遍即可。本题由于状态个数和状态之间的边不多,正常常数的 SPFA 不会被卡掉。

需要注意的是:在使用 BFS 搜索空格转移代价时不能经过目标棋子。
算法时间复杂度:$O(n^4)$

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×