TopCoder problem "Doorknobs" used in TCI '02 Round 2 (Division I Level Three)



Problem Statement

    

Tim and Tom are playing a game called Super-Doorknobs. From a starting position inside Tim's house, they each have to try to be the first one to touch a given number of doorknobs in any order. Tom, being aware of his disadvantage of not knowing Tim's house, decides to code up a quick algorithm to tell him which doorknobs to go after.

Given the configuration of the house and the number of doorknobs they need to hit, return the length of the shortest path that includes touching the necessary number of doorknobs.

The house configuration will be a String[] birds-eye view. The game will start in the top-left corner. The following characters will represent the house:

'.' - empty square.

'o' - square with a doorknob (they touch the doorknob the moment they enter this square).

'#' - a wall that neither of them can run through.

For example, if Tim and Tom were racing to touch 3 doorknobs in the following house configuration (quotes added for clarity):

{".....",
 "o....",
 "o....",
 "o....",
 "...o."}

The shortest path is straight down, and has a total length of 3. Therefore the method would return 3.

 

Definition

    
Class:Doorknobs
Method:shortest
Parameters:String[], int
Returns:int
Method signature:int shortest(String[] house, int doorknobs)
(be sure your method is public)
    
 

Notes

-If there is no way to reach <doorknobs> doorknobs from the starting location at the top-left of the house, return -1.
-Tim and Tom can only move up, down, left, or right. Diagonals are not allowed.
 

Constraints

-house will contain between 5 and 50 elements, inclusive.
-each element of house will be of length 5 to 50, inclusive.
-each element of house will be the same length as every other element of house.
-each element of house will contain only the characters '.', '#', and/or 'o'.
-the first character of the first element of house (the top-left square) will be a '.'.
-doorknobs will be between 1 and 4, inclusive.
-the number of 'o' characters in house is between <doorknobs> and 6, inclusive.
 

Examples

0)
    
{"....."
,"o...."
,"o...."
,"o...."
,"...o."}
3
Returns: 3
1)
    
{"....."
,"o...."
,"o...."
,"o...."
,"...o."}
4
Returns: 7
2)
    
{".#..."
,"#...."
,"...oo"
,"...oo"
,"...oo"}
1
Returns: -1
Tim and Tom can't move from the starting location (what an odd house).
3)
    
{"...o."
,"o..o."
,"....."
,"..oo."
,"....."}
4
Returns: 7
4)
    
{"....#"
,".##o#"
,".##oo"
,"o##.#"
,"....#"}
4
Returns: 12
5)
    
{"....#"
,"o##o#"
,".##oo"
,".##.#"
,"....#"}
4
Returns: 8
6)
    
{".................................................."
,".................................................."
,".................................................."
,".................................................."
,".................................................."
,".................................................."
,".................................................."
,".................................................."
,".................................................."
,".................................................."
,"...................o.............................."
,".................................................."
,".................................................."
,".................................................."
,".................................................."
,"........................................o........."
,".................................................."
,".................................................."
,".................................................."
,".................................................."
,".................................................."
,".................................................."
,".................................................."
,".................................................."
,".................................................."
,".................................................."
,".................................................."
,".................................................."
,"..........o......................................."
,".................................................."
,".................................................."
,".................................................."
,".....................................o............"
,".................................................."
,".................................................."
,".................................................."
,".................................................."
,".................................................."
,".................................................."
,".................................................."
,".................................................."
,".................................................."
,".................................................."
,".................................................."
,".................................................."
,".................................................."
,".................................................."
,".................................................."
,".................................................."
,".................................................."}
4
Returns: 106

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=979

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=4335&pm=979

Writer:

chogyonim

Testers:

alexcchan , lbackstrom

Problem categories:

Graph Theory, Search