## DWITE '12 R1 #5 - Haunted House

View as PDF

Points: 10
Time limit: 1.0s
Memory limit: 64M

Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig
##### DWITE, October 2012, Problem 5

Let's get one thing straight: Halloween is all about the candy. And Little Billy is determined to get all of it. However, one of the neighbours seems to have had the same idea. They constructed a Haunted House to hide all of their candy so that only the truly worthy can get them. Little Billy managed to get his hands on the floor plan of house, and realized that this was no ordinary haunted house: it seems to be full of fake walls. Being his only imaginary friend who can program, help Little Billy get as much candy as possible as quickly as possible.

The input will contain 5 test cases. The first line of each test case is an integer where , the number of rows and columns in the floor plan, followed by lines (each characters long), describing the floor plan.

• . - empty space
• # - unpassable wall
• - Billy's start location
• * - piece of candy
• (lowercase letters) fake walls

Fake walls are unlockable only if Billy has already collected at least as much pieces of candy as the order of the letter. That is, door "" requires at least piece of candy. "" = . "" = .

The output will contain 5 lines of output, each a pair of non-negative integers and . is the maximum number of candy pieces that Billy can collect. is the minimum number of steps to do so.

#### Sample Input

3
B.*
##b
..*
5
B...*
####a
.**..
#c#..
#*#..

#### Sample Output

1 2
4 11