TheLongWay | Topcoder Archive

Problem Statement

When all the presents are packed, Santa Claus has to deliver them to the children. He will start by delivering to the children in his own city. The city is a rectangular grid containing square blocks of equal size. You are given a String[] cityMap, where the j-th character of the i-th element is the block at row i, column j. There are four types of city blocks:

'S' - The block where Santa's home is located. This is his starting position.
'C' - A block where Santa must deliver presents to children. There are exactly 2 such blocks in the city.
'#' - A closed block occupied by a factory. Santa cannot enter these blocks.
'.' - An open block with no children.

It takes Santa one minute to move one city block north, south, east or west. He can only move in those four directions, and he cannot leave the city. When he enters a block containing children, he will deliver presents to all of them. This happens instantaneously and does not take any additional time. Since he doesn't want anybody to see him, he must change his direction after each minute and can make no stops. This means he can never make two consecutive moves in the same direction. Return the minimal number of minutes required for Santa to deliver presents to all the children in the city. If it is impossible, return -1 instead.

Definition

Class:: TheLongWay
Method:: minimalTime
Parameters:: String[]
Returns:: int
Method signature:: int minimalTime(String[] cityMap)
(be sure your method is public)

Constraints

cityMap will contain between 1 and 50 elements, inclusive.
Each element of cityMap will contain between 1 and 50 characters, inclusive.
All elements of cityMap will contain the same number of characters.
There will be exactly 2 characters 'C' in cityMap.
Each element of cityMap will contain only 'S', 'C', '#' and '.' characters.
There will be exactly one character 'S' in cityMap.

Examples

```
{"SCC",
 "..."}
```
```
Returns: 4
```
Santa cannot take a straight path because he must change his direction after every move.
```
{"C.C.S"}
```
```
Returns: -1
```
Mission is impossible.
```
{"#.#",
 "CSC",
 "#.#"}
```
```
Returns: 5
```
One of the optimal ways is: west, east, north, south, east.

{"#.#....",
 "##...#.",
 "C#...#.",
 ".....#.",
 "..#....", 
 "..#S.#.",
 ".##..#.",
 "###..##",
 "..C.#.#",
 "###.#.."}

Returns: 24

{
"#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#C",
".................S..................",
"C#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#"
}

Returns: 155

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.