Connection Status:
Competition Arena > Doorknobs

Doorknobs

TCI '02 Round 2 · 2002-10-16 · by alexcchan

TCI '02 Round 2 · 2002-10-16 · by alexcchan · Graph Theory, Search
Class Name: Doorknobs
Return Type: int
Method Name: shortest
Arg Types: (vector<string>, int)
Problem Statement

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.

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 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

Submissions are judged against all 40 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class Doorknobs with a public method int shortest(vector<string> house, int doorknobs) · 40 test cases · 2 s / 256 MB per case

Submitting as anonymous