Editorial for DMOPC '19 Contest 4 P2 - Pleasant Present

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: Riolku

In this problem, we note that there are only 4 relevant integers for a state. These are the position of the marble (2 integers, for the row and column indices) and the position of the current empty position (another 2 integers). Then, for each state, if the marble and empty position are adjacent, we can swap them.

We can also choose to swap the empty position with that of an adjacent position.

We also note that for each state, we only care about the fastest time required to reach that state. Therefore, we do Breadth-First-Search on the states. Our end state is any state where the marble is in the destination position.

Time Complexity: \mathcal O(N^4)


There are no comments at the moment.