样例输入

样例输出

题解

算法分析摘自《2013全国信息学奥林匹克年鉴》

算法分析

这道题主要考察同学们对最短路算法的理解。（我考试的时候怎么没看出来orz）
本题是一个很典型的最短路模型的题目。
假设我们把棋盘的局面当作结点，若A局面能通过一步变成B局面则将A局面和B局面对应的结点连上一条边权为1的边。那么问题就成了求这样建成的图中从初始局面对应的结点到达指定移动格在目标位置的局面对应的那些结点的最短路。也就是求边权都为1的途中的一个单源最短路，用BFS就可以解决这个问题了。具体做法如下：

用(EX,EY,MX,MY)表示空白格在(EX,EY)，指定移动格在(MX,MY)的局面所对应的结点。
1. 将(EX,EY,SX,SY)进队，将Distance(EX,EY,SX,SY)设为0。
2. 若队为空，则输出无解，算法结束。
3. 将队首元素取出，设为(EX,EY,MX,MY)。
- 若(MX,MY)等于(TX,TY)，则Distance(EX,EY,MX,MY)即为所求答案，算法结束。
- 否则，设由(EX,EY,MX,MY)能到达的局面(EX',EY',MX',MY')，且(EX',EY',MX',MY')从未进队过，则将(EX',EY',MX',MY')进队，将Distance(EX',EY',MX',MY')设Distance(EX,EY,MX,MY)+1，然后跳至步骤2.

可以知道，一个局面由空白格的位置和指定移动格的位置唯一确定，所以局面的数量是\(O((nm)^2)\)的，也就是说建成的图的结点数是\(O((nm)^2)\)的。由于每个局面只可能通过空格和上下左右的移动格交换来变成另外一个局面，所以建成的图中的边数也是\(O((nm)^2)\)的。因此求一次最短路的时间复杂度就为\(O(V+E)\)，即\(O((nm)^2)\)。但是询问有q次，所以总的时间复杂度为\(O(q(nm)^2)\)。

我们发现之间bfs不能满足题目的要求，所以算法还需要优化。

进一步分析可以发现，指定移动格只有当空白格在它附近才能移动，所以游戏的过程可以看成将空白格先移动到指定移动格附近（此处不考虑初始位置和目标位置相同的情况），然后指定移动格和空白格交换，再将空白格移动到指定移动格附近，然后再将空白格移动到指定移动格附近，然后再将指定移动格和空白格交换……如此循环下去，直至指定移动格达到目标位置。

如果只考虑空白格在指定移动格附近的局面，那这样的局面数显然是\(O(nm)\)的。而局面之间的转移我们只考虑两种，一种是交换指定移动格附近的位置（比如由上方移动到右方）。第一种转移只需要一步，而第二种转移所需的步数就等于固定指定移动格后将空白格移动所需的最小步数，这个步数可以bfs求出，且由于这样的bfs只有\(O(nm)\)种，且每种所需的时间是\(O(nm)\)，所以我们可以在\(O((nm)^2)\)的时间内预处理出来(或者像标程一样采用记忆化的方法)。

两种转移总共最多能转移到5个新的局面，所以暗张这样的局面来建图，点数和边数都是\(O(nm)\)的，但是边权就不是全为1了，所以需要用dijsktra算法来求最短路，时间复杂度为\(O(nm\times log(nm))\)。加上预处理，总的时间复杂度为\(O((nm)^2+nm\times log(nm))\)

至此，本题就完美地解决了。

代码

代码来自@ghj1222