Pond Skater 题解

思路

把每个可进入的格子看成图上的顶点。一次划水的代价始终为 $1$，所以应按广度优先搜索的层次求最短路。困难在于一个格子可能与同一行或同一列中至多 $K$ 个格子相连，直接枚举会在大网格上重复检查大量已经访问的格子。

对于较小网格，可以直接从每个出队格子向四个方向逐格扫描至多 $K$ 步。若 $K=1$，问题就是普通的四邻域网格广度优先搜索。

满分做法维护每一行和每一列中尚未访问的可进入格子。一次扩展先根据最近的荷叶和距离 $K$ 确定同一行、同一列真正可达的坐标区间，再只枚举区间内尚未访问的格子。格子第一次入队时同时从所在行和所在列的未访问集合中删除，因此之后不会被重复枚举。

做法

分别建立按行和按列编号的后继并查集。按行结构中的每个位置指向本行不小于它的第一个尚未删除位置；按列结构同理。初始化时删除所有荷叶和起点。另用四次线性扫描为每个格子记录同一行、同一列中最近荷叶限定的可移动边界。

广度优先搜索处理格子 $(x,y)$ 时，横向可达范围是荷叶边界与 $[y-K,y+K]$ 的交集。通过按行后继结构反复取得范围内第一个未访问格子，将其距离设为当前距离加一并入队，同时从两套后继结构删除。纵向范围用按列结构完全相同地处理。

正确性证明

荷叶边界与距离限制的交集恰好包含一次合法划水能到达的同一行或同一列格子，因此每次扩展不会加入非法位置。后继结构只跳过荷叶、起点或已经入队的格子；这些位置无需再次入队，所以不会漏掉任何尚未发现的合法邻居。

所有边的代价均为 $1$。广度优先搜索按距离不下降的顺序处理格子，格子第一次入队时得到的距离就是最短距离。删除该格子只阻止重复发现，不会影响从它继续扩展。于是终点若被发现，其距离就是最少划水次数；若搜索结束仍未发现终点，则不存在合法路径。

复杂度

每个格子至多在按行和按列结构中各删除一次，后继查询使用路径压缩。预处理与搜索的时间复杂度为 $O(HW\alpha(HW))$，空间复杂度为 $O(HW+H+W)$。