Connection Status:
Competition Arena > SecurityBunker

SecurityBunker

SRM 269 · 2005-10-26 · by Andrew_Lazarev

SRM 269 · 2005-10-26 · by Andrew_Lazarev · Graph Theory
Class Name: SecurityBunker
Return Type: double
Method Name: chooseBomb
Arg Types: (vector<string>)
Problem Statement

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.

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
0)
{"*.*",
 ".?.",
 "*.*"}
Returns: 1.4142135623730951

The answer is the distance from the secret object to any one of the bombs.

1)
{"*****", 
 ".?.?.",
 "..?..",
 ".?.?.",
 "*****"}
Returns: 3.0

With D>=1, the explosion of any bomb will explode all other bombs in the same row.

2)
{"*****",
 "....*",
 "....*",
 ".?..*",
 "....*",
 "*...*",
 "*****"}
Returns: 2.23606797749979
3)
{"*.*.*.*",
 ".?.?.?."}
Returns: 2.0

D=2 is enough to explode all bombs and the secret objects with them.

4)
{"?*..*?....?",
 "...........",
 "....*......",
 "...?.......",
 ".*....**?..",
 "*......?...",
 ".......*...",
 ".......?.*.",
 "..*.......*",
 "?........?.",
 "......?*?.."}
Returns: 5.0

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

Coding Area

Language: C++17 · define a public class SecurityBunker with a public method double chooseBomb(vector<string> field) · 145 test cases · 2 s / 256 MB per case

Submitting as anonymous