Or1on's blog

By Or1on, history, 6 years ago, In English

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.

  • Vote: I like it
  • +5
  • Vote: I do not like it

»
6 years ago, # |
Rev. 6   Vote: I like it 0 Vote: I do not like it

Check these references 1 and 2. There is also another version of this problem on UVa Online Judge that involves several instances of the shortest-path inside simple polygon problem in the same test.