ACM ICPC World Finals 2008

Problem D: The Hare and the Hounds

The hound has two different modes of operation. In its standard mode, it is simply trying to get to the endpoint by following the main road rule. Whenever it gets to a choice point, it switches to the “confirmation mode”, in which it is only searching for a confirmation marker (by trying different exits from the choice point intersection, each time following the main road rule until it has become apparent that the wrong exit from the choice point intersection was taken). Once it finds the confirmation marker, it switches back to the standard mode and continues as before.