Блог пользователя Or1on

Автор Or1on, история, 6 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

»
6 лет назад, # |
Rev. 6   Проголосовать: нравится 0 Проголосовать: не нравится

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.