Editorial for Back To School '19: Parkour

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.

Author: Zeyu

Subtask 1

For the first subtask, we can get the shortest path from Wesley's house to the school using a breadth-first search.

Time Complexity: $\mathcal{O}(XY)$ ~\mathcal{O}(XY)~

Subtask 2

For the second subtask, one can observe that the order of the moves does not impact the destination. We can then try to fix the number of move 1s that Wesley uses to find the minimum number of move 2s that allow us to reach the school. There may be cases where you need to readjust the move 1s to satisfy the school boundary. If the sum of move 1s and 2s is strictly less than $T$ ~T~, then the answer will be YES. Otherwise, it will be NO.

Time Complexity: $\mathcal{O}(T)$ ~\mathcal{O}(T)~

Bonus

Can you solve the problem in $\mathcal{O}(1)$ ~\mathcal{O}(1)~?

Comments

There are no comments at the moment.