如果在 $(x_s,y_s)$ 和 $(x_t,y_t)$ 形成的矩形中没有障碍，则答案为 $|x_s-x_t|+|y_s-y_t|$；否则，如果存在路径，可以证明存在一条最短路经过某个障碍点相邻的格子。预处理以每个这样的格子为起点的最短路即可。
时间复杂度 $O(k(nm+q))$。
QOJ.ac
QOJ
As we are currently experiencing an overwhelming number of web requests for fetching user submissions, we have temporarily disabled the full submissions list. You must now be logged in to view submissions.
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.