FatMaze | Topcoder Archive

Problem Statement

Your team is stuck in a maze. The 'P' characters in maze show where your group is located. The 'X' characters are walls, the 'G' characters are goals, and the '.' characters are empty spots. Taking 1 step involves moving every 'P' character 1 space upward, leftward, rightward, or downward. All of the 'P' characters must move in the same direction. A step cannot cause any 'P' character to cover an 'X' character, or leave the confines of the maze. When any 'P' character covers a 'G' character you are done. Return the least number of steps required to finish the maze. If finishing is not possible, return -1. Note that the maze need not be rectangular, and that the left edges are always aligned.

Definition

Class:: FatMaze
Method:: minSteps
Parameters:: String[]
Returns:: int
Method signature:: int minSteps(String[] maze)
(be sure your method is public)

Constraints

maze will contain between 1 and 10 elements inclusive.
Each element of maze will contain between 1 and 10 characters inclusive.
Each character in maze will be 'X', '.', 'G', or 'P'.

Examples

{"PP",
 "PP",
 "..",
 "..",
 "..",
 "..........",
 ".........G"}

Returns: 13

Remember you cannot leave the confines.

{"PP",
 "PP",
 "..",
 "..",
 "..",
 ".........",
 ".........G"}

Returns: -1

The goal is in a corner we cannot fit into.

{"P.X",
 "P.X",
 "P.X",
 "P.X.....PG"}

Returns: 1

One of us has managed to sneak by the wall.

{"P",
 "PP",
 "PPP",
 "....",
 "X....",
 "XX....",
 "XXX....",
 "XXXX...G"}

Returns: 10

```
{"PP....GGGG"}
```
```
Returns: 5
```
```
{"G"}
```
```
Returns: -1
```

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.