//注意这里讲的是A*算法,如果没学过A*的童鞋请自行百度一下哦~

1. 题目

传送门= ̄ω ̄=

2. 题解

貌似网上题解主要都是bfs+spfa。。。

详见KB的题解:[戳这里~]

这种做法太强啦Orz%%%%%%%蒟蒻我完全想不到啊!!!

我记得很久以前我就刷这题了,当时一眼看过去——A*呗!简直和八数码问题一模一样!

燃鹅,当时的我太naive,写的hash函数也是too young。这题有多组数据,光清空哈希表都TLE了。

最近刷NOIP历年题目发现了这个只拿了50分的题,于是开始重新写。

好!现在进入正题了!

0. 一些重要的东西

  • 显然,如果我们要移动指定棋子,那么必须满足空格在其旁边(上下左右)
  • 因此我们可以在开始的时候跑bfs计算让空格移动到指定棋子旁边的代价是多少。
  • 我们设$dis(x1,y1,x2,y2,d)$为当空格在位置$(x1,y1)$,指定棋子在$(x2,y2)$,把空格移动到指定棋子的方位d的代价。
  • 我们用0表示下方,1表示上方,2表示左方,3表示右方
  • 我们可以预处理出$dis(i-1,j,i,j,d),dis(i+1,j,i,j,d),dis(i,j-1,i,j,d),dis(i,j+1,i,j,d),d\in [0,4]$,即处理出对于指定棋子所在的位置$i,j$,空格在它的上、下、左或右时,将空格移动到指定棋子的上、下、左和右的代价。这样方便快速地进行状态的扩展。

1. 估价函数$h(n)$

我取的估价函数就是最普通的估价函数——指定棋子到目标位置的曼哈顿距离作估价函数值。

2. 实际代价函数$g(n)$

即当前状态已经移动了多少步。

3. OPEN表

就是弄一个优先队列(priority_queue)。根据每个状态的估价函数$h(n)$与实际代价函数$g(n)$的和,每次取出最小的。

4. Hash表

为了判重我们需要一个Hash表来排除没用的状态。

我们设一个状态为state,state.h表示当前状态中指定棋子所在的行数,state.w表示当前状态中指定棋子所在的列数,state.d表示空格在指定棋子的方位(0或1或2或3)。

那么我们让$hash\_table(state.d,state.h,state.w)=min{g(state)}$

hash_table指的是哈希数组,g表示实际代价函数

这里的哈希表映射出来的不能使bool型(即是否访问过),而应该是int型,保存实际代价函数的值。

为什么呢?因为我们的估价函数只是个“估计值”,存在误差。所以我们需要进行类似于spfa的“松弛”操作。即可能有两个状态,它们的行数、列数、方位都相同,因此它们的估价函数也一定相同。但是可能存在它们的实际代价函数不同。当出现这种情况,显然是实际代价函数小的那个更优,而另一个也就不用考虑了。

所以如果我们直接用bool型来hash行数、列数、方向的话,就无法判断哪个的花费更小,是否应该将当前状态加入优先队列了。

等于hash_table中存的是每个状态最小的实际代价(如果没出现某个状态则为无限大)。

如果发现某个状态之前出现过了,但是它的实际代价更小,那就更新hash_table中这个状态的最小值,并将这个状态加入优先队列。

5. 具体实现

  1. 读入一个01矩阵后进行bfs预处理
  2. 读入空格位置、起点位置、终点位置。将“把空格移动到起点的旁边”后的状态加入OPEN表(优先队列)中。
  3. 当OPEN表不为空:
    • 取出OPEN表中最优的状态。
    • 扩展状态(将空格移动到指定棋子的上、下、左、右方或交换空格与指定棋子的位置)
    • 对于每种扩展出来的状态,去hash_table里查对应的值。如果查出来的值比当前状态的实际代价大,就把当前状态放到OPEN表中,并且更新hash_table中对应的值。
    • 如果某个时刻发现当前状态中指定棋子的位置等于终点位置,直接输出这个状态的实际代价即可。
  4. 如果OPEN表空了而且还没找到答案则误解,输出-1。

6. 注意事项

  • 清空hash_table
  • 如果起点等于终点直接输出0
  • 注意常数问题(雾)

7. 辣鸡代码