DWITE Online Computer Programming Contest

Haunted House

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 file DATA5.txt will contain 5 test cases. The first line of each test case is an integer 3 ≤ N ≤ 10, the number of rows and columns in the floor plan, followed by N lines (each N characters long) describing the floor plan.

Fake walls are unlockable only if Billy has already collected at least as many pieces of candy as the order of the letter. That is, door “a” requires at least 1 piece of candy, “b” requires 2, etc., “f” requires 6.

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

Sample Input (first 2 shown):
Sample Output (first 2 shown):
1 2
4 11

Explanation of sample: In the first case, Billy collects the first piece on the second step, but that’s not enough to make it through the wall "b". In the second case, Billy is able to collect all 4 pieces of candy.