Editorial for New Year's '17 P2 - Peter's Escape


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

There are two possible solutions: generating an adjacency matrix and then performing a breadth first search, or sorting the coordinates by x-value and y-value and performing binary search in conjunction with a breadth first search. We will be focusing on the latter solution.

Store all the obstacles and exits in two vectors: one sorted by the x-coordinates and one sorted by y-coordinates. Perform a breadth first search, using binary search to find the next obstacle/exit to the left, right, up, and down.

Time Complexity: \mathcal{O}(\sigma \log \sigma), where \sigma=O+E is the number of obstacles and exits


Comments

There are no comments at the moment.