SecurityBunker | Topcoder Archive

Problem Statement

You will be given a map of the bunker. The map will consist of bombs ('*'), empty cells ('.') and secret objects ('?') arranged on a regular grid. For security reasons, in case of danger, all secret objects in the bunker should be destroyed by the explosion of any one bomb. A bomb explosion destroys all objects in range D, where D depends on the bomb type. A bomb explosion also causes all other bombs in range D to explode. More formally, an item (a secret object or a bomb) will be affected by a bomb explosion if the distance between the centers of their cells is not greater than D.

You will be given a String[] field. Return the minimal value of D that will ensure that all secret objects will be destroyed by the explosion of any one bomb.

Definition

Class:: SecurityBunker
Method:: chooseBomb
Parameters:: String[]
Returns:: double
Method signature:: double chooseBomb(String[] field)
(be sure your method is public)

Notes

The returned value must be accurate to 1e-9 relative or absolute.

Constraints

field will contain between 1 and 50 elements, inclusive.
Each element of field will contain between 1 and 50 characters, inclusive.
Each element of field will contain the same number of characters.
field will contain only the characters '*', '.', and '?'.
field will contain between 1 and 100 '*' characters, inclusive.
field will contain between 1 and 100 '?' characters, inclusive.

Examples

```
{"*.*",
 ".?.",
 "*.*"}
```
```
Returns: 1.4142135623730951
```
The answer is the distance from the secret object to any one of the bombs.
```
{"*****", 
 ".?.?.",
 "..?..",
 ".?.?.",
 "*****"}
```
```
Returns: 3.0
```
With D>=1, the explosion of any bomb will explode all other bombs in the same row.

{"*****",
 "....*",
 "....*",
 ".?..*",
 "....*",
 "*...*",
 "*****"}

Returns: 2.23606797749979

```
{"*.*.*.*",
 ".?.?.?."}
```
```
Returns: 2.0
```
D=2 is enough to explode all bombs and the secret objects with them.

{"?*..*?....?",
 "...........",
 "....*......",
 "...?.......",
 ".*....**?..",
 "*......?...",
 ".......*...",
 ".......?.*.",
 "..*.......*",
 "?........?.",
 "......?*?.."}

Returns: 5.0

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.