1376: 向量场寻路算法

题目背景

游戏开发中常提到“向量场寻路（Vector Field Pathfinding）”这个听起来高大上的算法。出题人打赌你们可能没有听过，而立志成为游戏客户端工程师的 ShadowDrunk 在研究了这个算法的底层原理后，坚定地认为：“这本质上不就是个基础的图论搜索遍历算法嘛！取这么个奇葩名字真是不好评价。”

今天，有一位同学拿着他用 Unity 制作的坦克大战 Demo 给 ShadowDrunk 看，并自豪地介绍他用 A* 算法实现了敌方坦克的寻路。虽然 A* 在游戏中应用广泛且有诸多变种，但在面对“地图上大量敌人同时追击玩家”的场景时，单体 A* 会带来巨大的性能开销。于是，ShadowDrunk 立刻想到了本题所描述的这个神奇算法。

题目描述

给定一个 $n \times m$ 的网格地图，其中 . 表示空地，# 表示障碍物。地图中存在一名玩家，坐标记录为 $(X_{player}, Y_{player})$，同时存在 $k$ 个敌方坦克，第 $i$ 个敌人的坐标为 $(X_i, Y_i)$（$1 \le i \le k$）。

玩家和敌人都只能在空地上进行上下左右四个方向的移动，且无法穿过障碍物。

你需要设计一个算法，首先求出所有敌方坦克到达玩家位置的最短距离。

随后会有多次询问，你需要求出指定的敌人坦克到达玩家位置的最短路径。由于最短路径可能有多条，请输出字典序最小的一条最短路径。

路径表示与字典序规则：

• 路径由数字 1, 2, 3, 4 组成，分别代表：1-向上走，2-向下走，3-向左走，4-向右走。
• 字典序比较规则为逐位比较，单个元素的大小关系为 1 < 2 < 3 < 4。例如 123 < 143，12 < 123。

注意：本题的路径查询部分强制在线，具体的加密规则见输入格式。

第一行包含两个整数 $n, m$（$n \times m \le 10^6$），代表地图的大小。

第二行包含两个整数 $x, y$（$1 \le x \le n, 1 \le y \le m$），代表玩家所在的坐标。

接下来 $n$ 行，每行包含 $m$ 个字符，用于表示地图网格（. 表示空地，# 表示障碍）。

接下来一行包含一个整数 $k$（$1 \le k \le \text{空地的数量}$），代表敌方坦克的数量。

接下来 $k$ 行，每行包含两个整数 $x_i, y_i$，代表第 $i$ 个敌人的坐标。

接下来一行包含一个整数 $q$（$1 \le q \le 10$），代表查询的次数。

接下来 $q$ 行，每行给出一个整数 $ind_{now}$，代表加密后的查询序号。

强制在线解密规则：

设上一次查询的真实序号为 $ind_{last}$（如果是第一次查询，则给出的 $ind_{now}$ 就是真实序号），本次查询的真实序号 $ind_{true}$ 计算公式为：

其中，$dis[x]$ 代表第 $x$ 个敌人到达玩家的最短距离。你需要输出第 $ind_{true}$ 个敌人到达玩家字典序最小的最短路径。若上一个敌人无法到达则距离视为 $-1$。即此时$dis[ind_{last}] = -1$。

第一行输出 $k$ 个整数（以空格分隔），代表 1 到 $k$ 号敌人到达玩家的最短距离。

如果该敌人无法到达玩家位置，最短距离输出 -1，且路径查询输出 -1。

接下来输出 $q$ 行，每行输出对应解密后的敌人到玩家的一条字典序最小的最短路径（操作序列以空格分隔）。无法到达则输出 -1。

5 5
1 1
...#.
.....
##.##
.....
.....
3
3 3
2 2
5 5
2
1
2194187

4 2 8
1 1 3 3
1 3 3 1 1 1 3 3