如果在 $(x_s,y_s)$ 和 $(x_t,y_t)$ 形成的矩形中没有障碍，则答案为 $|x_s-x_t|+|y_s-y_t|$；否则，如果存在路径，可以证明存在一条最短路经过某个障碍点相邻的格子。预处理以每个这样的格子为起点的最短路即可。
时间复杂度 $O(k(nm+q))$。
QOJ.ac
QOJ
Discussion #222 for Problem #9297. Labyrinth
Type: Editorial
Status: Open
Posted by: jiangly
Posted at: 2025-12-13 00:17:59
Last updated: 2025-12-13 00:18:03
题解
Comments
No comments yet.