OK, maybe stealing the Duchess's favorite ruby necklace was not such a good idea. You were making your way toward the city gates when you heard the sound you had been dreading: a sharp whistle followed by an answering bark. You know that the constable has just fetched his favorite hound and is starting to search for you. They might head straight for a gate. They might try to pick up your trail on the way. You really can't guess. But if they reach the gate before you, you're caught. If they happen across your trail, the hound will pick up your scent. The dog knows your scent already - this isn't your first offense! The constable will loose the hound, who can run fast once he has the trail to follow.
You have a dilemma. If you are absolutely sure that you can reach the gates before the guard and before being overtaken by the hound, you can keep the necklace. But if you aren't sure, you need to drop the necklace right now into the nearest pile of rubbish and saunter casually away. Even if they grab you, without the necklace in your hands they will eventually release you.
So, keep the necklace or drop the necklace?
The town is modeled as a rectangular maze of discrete squares. It is surrounded by a wall that contains one or more exits. You know, of course, your own position within the town. You also know the location of the kennel where the constable and the hound start out.
Input consists of one or more mazes. Each maze begins with a line containing two integers, W and H, denoting the width and the height of the maze. End of input is indicated when either of these values is less than 3. Neither dimension is greater than 50.
This is followed by H lines of input, each containing W characters.
The interpretation of the characters in these lines is as follows:
All mazes will be completely enclosed by a combination of X and E characters. There is at least one path between the kennel and you, and there is at least one path between you and each exit.
For each maze, print a single line of output. If there is a path that you can take that will guarantee that you can escape, no matter what path what the constable and hound take, then print KEEP IT. If there is no path that offers such a guarantee, print DROP IT.
19 11 XXXXXXXXXXXXXXXXXXX X X E X X XXX XXX K X X X X X X X X X X X T X X X X X X X XXXXXXX X X X XXXXXXXXXXXXXXEXXXX 19 11 XXXXXXXXXXXXXXXXXXX X X E X X XXX XXX K X X X X X X X X X X X T X X X X X X XXXXXXX X X X XXXXXXXXXXXXXXEXXXX 0 0
DROP IT KEEP IT
In the first case, the constable and his hound can discover, on turn 7, the space where the thief had stood on turn 4. The hound is loosed and overtakes the thief on turn 10 (or earlier if the thief doubles back).
In the second case, the thief can reach the city gate in 13 turns, at which point the constable and hound hit his trail. However, the thief is still able to get out of the city before the hound catches him.