Needing Help on a Polish OI Problem

Revision en1, by Or1on, 2018-11-27 06:26:44

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.

Tags geometry, dijkstra

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English Or1on 2018-11-27 06:26:44 716 Initial revision (published)