Editorial for ICPC NEERC 2012 L - Labyrinth of the Minotaur

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.

The key fact to the solution:
- If one traverses the path from the entrance to the lair using left-hand rule and using right-hand rule, then an obstacle blocks all paths from the entrance to the lair if and only if it blocks both left-hand and right-hand paths
Precompute the number of blocked cells and the number of cells visited by each path in each rectangular $(1, 1) \dots (x, y)$ ~(1, 1) \dots (x, y)~ region
- This way, one can find the corresponding number in each rectangular $(x_1, y_1) \dots (x_2, y_2)$ ~(x_1, y_1) \dots (x_2, y_2)~ region in $\mathcal O(1)$ ~\mathcal O(1)~ time
For each $(x, y)$ ~(x, y)~, use binary search to find the smallest square that blocks both left and right path; check that the resulting square is not blocked by any obstacles

Comments

There are no comments at the moment.