TopCoder problem "TheLongWay" used in TCHS09 Final Round (Division I Level Two)



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

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

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10280

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13731&pm=10280

Writer:

Vasyl[alphacom]

Testers:

PabloGilberto , Olexiy , ivan_metelsky

Problem categories:

Dynamic Programming