TopCoder problem "DriveCar" used in TCHS SRM 44 (Division I Level Two)



Problem Statement

    

Little John likes to play driving games. One of his favorite games involves a horizontal three-lane road divided into cells. The cells are numbered 0, 1, 2, etc. from left to right, and the lanes are numbered 0, 1, 2 from top to bottom. The car is initially located in the middle lane in the leftmost cell (lane 1, cell 0). The goal of the game is to reach any lane of the rightmost cell without hitting any obstacles or leaving the road.

The car moves horizontally one cell at a time. Each time it moves to the next cell, it can either stay in the same lane or move diagonally to an adjacent lane. More formally, if the car is in lane i, cell j, then after the next move, it can be in one of the following lanes of cell j+1: i, i-1 (only if i>0), or i+1 (only if i<2).

The road is given as a String[] road, where the j-th character of the i-th element is the content of lane i, cell j. '.' represents open road and '#' represents an obstacle. The car hits an obstacle if it ends a move on a '#' character. Return the fewest number of lane changes necessary to reach the rightmost cell without hitting any obstacles or leaving the road. If it is impossible to reach the rightmost cell, return -1 instead.

 

Definition

    
Class:DriveCar
Method:minNumberOfDrifts
Parameters:String[]
Returns:int
Method signature:int minNumberOfDrifts(String[] road)
(be sure your method is public)
    
 

Constraints

-road will contain exactly 3 elements.
-All elements of road will contain the same number of characters.
-Each element of road will contain between 1 and 50 characters, inclusive.
-Each character in each element of road will be '.' or '#'.
-The leftmost character of element 1 of road will be '.'.
 

Examples

0)
    
{"....",
 "....",
 "...."}
Returns: 0
John doesn't need to change lanes to win the game: 
       ....      ....      ....      ....
start  C...  ->  .C..  ->  ..C.  ->  ...C
       ....      ....      ....      ....
1)
    
{"#.###.##",
 ".#.#.#.#",
 "###.###."}
Returns: 7
#.###.##    #C###.##    #.###.##    #.###.##    #.###.##    #.###C##    #.###.##    #.###.##
C#.#.#.# -> .#.#.#.# -> .#C#.#.# -> .#.#.#.# -> .#.#C#.# -> .#.#.#.# -> .#.#.#C# -> .#.#.#.#
###.###.    ###.###.    ###.###.    ###C###.    ###.###.    ###.###.    ###.###.    ###.###C -> end
2)
    
{"..#....#..#.#...#..",
 "...#.#...#.#..#..#.",
 ".##..........#...#."}
Returns: 5
3)
    
{"#..#.#.##.",
 ".#.#...##.",
 ".###.##.#."}
Returns: -1
John can't reach the end of the road.

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10795&pm=8250

Writer:

boba5551

Testers:

PabloGilberto , brett1479 , Olexiy , ivan_metelsky

Problem categories:

Dynamic Programming, Graph Theory