Editorial for ECOO '13 R3 P3 - Go With the Flow


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.

This can be solved with a standard backtracking path search algorithm, with a couple of twists. The first twist is that when you find a goal you have to switch targets and continue until you have found all the targets, but you still need to be able to backtrack right back to the beginning. (In my solution, I counted the targets first so I knew when I was finished.) The second twist is that before you declare victory you have to check to make sure your solution used all the grid squares. If not, you have to backtrack and continue. The boards are small and highly constrained because of the number of targets, so a properly implemented solution should finish very quickly, well within the 10 seconds allotted for each board. In fact, the boards are so constrained that one team got 7 out of 10 correct without using backtracking.


Comments

There are no comments at the moment.