DWITE Online Computer Programming Contest
common problem is being chased through a maze by a hungry velociraptor. There is no time to think as to how one came to be in such a situation. A program is required to calculate the survival time of a human character.
The maze consists of hallways, and has no open areas. There are no loops in the maze - that is, there is always only one possible path between any two points. There is just one exit, one human, and one velociraptor present in the maze. The only possible chance of survival is to make it to the exit before the velociraptor does. The velociraptor will also run towards the exit, covering twice as much ground "per turn" as the human figure.
Note: the velociraptor has no intelligence, but it knows its way to the exit. It will attack only when it occupies the same "square" as a human. In a case when the velociraptor is between a human and the exit, both will continue running until they meet at the exit location.
InputThe first line of input contains an integer R (0 < R ≤ 10), the number of rows in the maze. The second line contains an integer C (0 < C ≤ 10), the number of columns in the maze. R lines follow, each describing one row of the maze. '#' represents a wall, '.' an open space, 'E' the exit, 'H' the human, and 'V' the velociraptor.
OutputA single line containing the result. If the human reaches the exit before the velociraptor, output "escape". Otherwise, output the number of steps the human took before being caught by the velociraptor. Note that this will always be at least one. If the velociraptor reaches the exit before the human, it will wait there until the human arrives. If they reach the exit at the same time, the human is still caught.
Sample Input 1
3 5 ##### V..HE #####
Sample Output 1
Sample Input 2
3 5 ##### H..EV #####
Sample Output 2
Point Value: 10 (partial)
Time Limit: 2.00s
Memory Limit: 16M
Added: Mar 20, 2010
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3