TombExplorer | Topcoder Archive

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?

Definition

Class:: TombExplorer
Method:: minimumDigging
Parameters:: String[]
Returns:: int
Method signature:: int minimumDigging(String[] map)
(be sure your method is public)

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

```
{"XXX",
 "X.X",
 "XXX"}
```
```
Returns: 0
```

{"XXXXX",
 "X.X.X",
 "XXXXX"}

Returns: 1

```
{"...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.)

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.