FireDrill | Topcoder Archive

Problem Statement

The locations of the people and obstacles in a rectangular area are known. How much time is required to get them all out? Fire regulations require that they can all leave the area within one minute.

The area is treated as a rectangular grid of squares. We will treat time in discrete seconds. At each second each person can

move to an adjacent (not diagonally) square
stay in her current square
leave the area, if she is adjacent to the border

A square may be occupied by at most one person at a time, but a person can enter a square at the same time that a different person is leaving it.

The initial configuration is given by a String[] area showing the contents of each square: '-' means empty, 'p' means person, 'x' means obstacle. Obstacles never move and a square with an obstacle cannot be occupied by a person. Given area, return the minimum time required to get all the people out of the area. Return -1 if the minimum time is greater than 60 seconds.

Definition

Class:: FireDrill
Method:: minTime
Parameters:: String[]
Returns:: int
Method signature:: int minTime(String[] area)
(be sure your method is public)

Notes

A return value with either an absolute or relative error of less than 1.0E-9 is considered correct.

Constraints

area will contain between 2 and 20 elements, inclusive.
Each element of area will contain the same number of characters, between 2 and 20, inclusive.
Each character in each element of area will be '-', lowercase 'p', or lowercase 'x'.
The total number of 'p's in area will be between 1 and 20, inclusive.

Examples

```
{ "pppp",
  "pppp"
         }
```
```
Returns: 1
```
These people can each step out of the area immeidately.
```
{ "xxx",
  "xpx",
  "xxx" }
```
```
Returns: -1
```
The one person has no exit route.
```
{ "pp",
  "pp",
  "xx" }
```
```
Returns: 1
```
Each person can move horizontally out of the room.
```
 {"xxx",
  "xpx",
  "xpx",
  "xp-",
  "xpx",
  "xxx"}
```
```
Returns: 5
```
With a little cooperation one person can exit every second from the single exit, except for the first second.

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.