Connection Status:
Competition Arena > TombExplorer

TombExplorer

TCC19 South America Prelims · 2019-06-10 · by erinn

TCC19 South America Prelims · 2019-06-10 · by erinn · Graph Theory
Class Name: TombExplorer
Return Type: int
Method Name: minimumDigging
Arg Types: (vector<string>)
Problem Statement

Problem Statement

You are preparing to explore a newly discovered tomb. Fortunately, due to some modern technology, you have a map of what the tomb looks like. Some areas are clear, and others are filled with debris. You are given this String[] map. An 'X' indicates debris, while a '.' indicates a clear area.

The tomb is divided into as many as six chambers. A chamber consists of clear areas adjacent to each other vertically or horizontally. Once inside the tomb, you can move around vertically and horizontally. It takes no effort to move through clear areas as many times as you like, but moving through any debris filled area takes effort each time you travel through it.

You plan to dig a single entrance and a single exit to the tomb, at locations of your choosing. (In other words, you may start and end your exploration of the tomb in any area you like. The entrance and the exit may be at the same location.)

Assuming you make an optimal selection, what is the fewest times you must travel through debris-filled areas in order to visit every clear area of the tomb at least once?

Constraints

  • map will contain between 1 and 50 elements, inclusive.
  • Each element of map will contain the same number of characters, between 1 and 50 inclusive.
  • Each characer of each element of map will be '.' or 'X'.
  • The empty areas will form between 1 and 6 chambers, inclusive.
Examples
0)
{"XXX",
 "X.X",
 "XXX"}
Returns: 0
1)
{"XXXXX",
 "X.X.X",
 "XXXXX"}
Returns: 1
2)
{"...XX...",
 "...XXXX.",
 "XXXXXXX.",
 "XXXXXXX.",
 "XXXXXXX.",
 "XXXXXXX.",
 "XX.XXXX.",
 "XXXXXXX.",
 ".X.X.X.."}
Returns: 7

The chambers look as follows: 111XX222 111XXXX2 XXXXXXX2 XXXXXXX2 XXXXXXX2 XXXXXXX2 XX3XXXX2 XXXXXXX2 4X5X6X22 One optimal solution is to enter the tomb anywhere in chamber 1, then go to chamber 2 (through 2 debris cells), from there to chamber 6, 5, 4, back to 5, and finally to chamber 3 from where we exit the tomb. The total number of traversed debris cells is 7. (Note that the debris cell between chambers 4 and 5 is entered and also counted twice.)

3)
{".X.X.X",
 "X.X.X."}
Returns: 5
4)
{"XX..XX",
 "XXXXXX",
 ".X..X.",
 ".X..X.",
 "XXXXXX",
 "XX..XX"}
Returns: 6

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

Coding Area

Language: C++17 · define a public class TombExplorer with a public method int minimumDigging(vector<string> map) · 23 test cases · 2 s / 256 MB per case

Submitting as anonymous