Hounded by Indescision

First thing to realize is that we can only keep the necklace if there is some path we can take such that the dog can never reach us regardless of the path he takes. Second thing to realize is that if the dog is closer to the exit than us, we can never keep the necklace.

For a path to be a valid path, it means that for every square along the path, if the dog walked straight to that square and then followed us to the exit (at double speed of course), he would not catch us. It follows that if a square is invalid when the path covers the shortest distance from that square to the exit, it must be invalid for ALL paths from that square to the exit (since making the path longer simply gives the hound more time to "catch up"). Therefore, if we can determine invalid squares, they should be viewed as barriers to us (but not to the dog).

1. bfs from us to the exit
2. determine if the path is valid
   1. iterate over every square in the path
   2. calculate the distance from the dog to that square (BFS)
   3. calculate if the dog can reach us if he intersects the trail at that point
3. if the path is not valid, remove the invalid points from consideration for all future paths
4. repeat

Note: we cannot reuse ANY data from the bfs to find the path, since we don't know for sure which paths depended on the squares we now marked as invalid....better to just recompute.

Runtime: at worst we mark 1 square as invalid at each iteration, meaning we could need 1600 iterations. Each iteration takes time 1600 to do the BFS (worst case...it's actually less than half of that). Then for each iteration we have to bfs from the Dog to the path...another 1600...i'm not sure exactly how much optimization you would need, but I would precompute the distance from the dog to every point to avoid having to calculate it. We're probably fast enough. In any case, that makes it O(n^2) where there are n total squares. plenty fast enough.