Magical Protection

Here's the rundown. Harry is good, but he's just a kid, and his magic is weak. Voldemort is evil, and his magic is strong. Dumbledore is good, and his magic is the most powerful of all. Harry, Voldemort, and Dumbledore are in a square grid maze. Voldemort wants to move from his location to Harry's location. If he makes it to Harry's location, Voldemort can kill Harry. BUT if Voldemort ever visits Dumbledore's location or one of the up to eight squares adjoining Dumbledore's location (horizontally, vertically, or diagonally), Dumbledore will subdue Voldemort before Voldemort can kill Harry. Voldemort can move horizontally and vertically (but not diagonally). Harry and Dumbledore cannot move at all.

Given an input maze, you are to print out whether Voldemort can bypass Dumbledore to get to Harry. Voldemort is not an idiot; he will not go past Dumbledore if it is possible to get to Harry another way.

Input Specification

The input will consist of series of mazes. Each maze will consist of r lines, each containing c characters. r and c will be inclusively between 2 and 20. Most of the characters will be either '1' (indicating a boundary) or '0' indicating a free square in the grid. There will be exactly one 'H', exactly one 'D', and exactly one 'V', corresponding to Harry's location, Dumbledore's location, and Voldemort's initial location. Each maze will be followed by an empty line (so that there will appear to be a skipped line between mazes in the input). The last maze in the input will be followed by a second empty line.

Output Specification

The output cases are to appear in the same order in which they appear in the input. For each maze, you are to print either “Voldemort can kill Harry.” or “Voldemort cannot kill Harry.”, whichever is appropriate. These sentences should each be terminated by exactly one newline character. As always, formatting counts! Make sure everything is spelled correctly!

Sample Input

1. 000000
2. 000000
3. 0H0000
4. D00000
5. 000V00
7. 00000D
8. 000000
9. 0H0000
10. 000000
11. 000V00

download as text file

Output for Sample Input

1. Voldemort cannot kill Harry.
2. Voldemort can kill Harry.

download as text file

Original Problem

NMU Invitational Programming Contest, 2001