I've been struggling with problem Castle on Polish OI III lately and since the editorial is in Polish and it was a scanned version of the book so I couldn't translate the solution perfectly.

Here is the link to the problem: https://szkopul.edu.pl/problemset/problem/ax-Clr28s2FRg9-X4Z1v1Nx9/site/?key=statement

I was thinking of creating a graph with edges that connects the vertices of the polygon that only exists if there is a path with length equal to the Manhattan distance of the two vertices and then run Dijkstra to get the shortest path but the problem is that I couldn't check the existence of such edges. I would really appreciate any help. Thank you very much.