TopCoder problem "PaperRacing" used in SRM 352 (Division I Level Three)

Problem Statement

Alice and Bob often play the following car racing "sim". To represent the track they take a sheet of paper, split it into square cells and make each cell either a "road" or "obstacle". Two of the "road" cells are marked as "Start" and "Finish", and the goal of the game is to move your car from the start to the finish as fast as possible.

In this paper game, the car is represented by a point, which moves in turns. At the beginning of each turn the car is located at the center of some cell, and each turn moves the car to the center of some other cell. The speed of the car is represented by a vector with integer coordinates. Each turn consist of two parts:

Change the speed of your car, modifying the speed the car had before this turn. Each coordinate of the speed can be increased by 1, decreased by 1 or left unchanged.
Move the car. If the car has coodinates (row, col) and its speed is (vRow, vCol), then its new coordinates will be (row + vRow, col + vCol). The car moves along the straight line between the centers of the old and new cells.

When the path of the car touches the "Finish" cell, it immediately finishes and the time it spent for the race is the number of turns it took (counting the final one). If the path of the car intersects an obstacle before it is finished, then the car crashes and can not finish the race (the car can touch obstacles, see examples for clarification). The car can not leave the grid because it will lead to disqualification. Please note that the car finishes immediately when it touches the Finish cell, and the car successfully finishes even if continuing the turn would move it outside the track or into an obstacle.

You will be given a String[] track, representing the track where the race occurs. Character j of element i of track represents the cell at (i, j). '.', 'S', 'F' and 'X' characters represent free road, start, finish and obstacle, respectively. You are also given two ints, vRow and vCol, representing the initial speed of the car. Return the minimal number of moves needed to finish the race. Positive direction of vRow means increasing the row number and positive direction of vCol means increasing the column number (see examples 1 and 2). If it is not possible to get to the finish cell from the start cell without crashing, return -1.

Definition

Class:	PaperRacing
Method:	minMoves
Parameters:	String[], int, int
Returns:	int
Method signature:	int minMoves(String[] track, int vRow, int vCol)
(be sure your method is public)

Constraints

track will contain between 1 and 50 elements, inclusive.

Each element of track will contain between 1 and 50 characters, inclusive.

All elements of track will contain the same number of characters.

Each element of track will contain only '.', 'X', 'S' and 'F' characters.

track will contain exactly one 'F' and one 'S'.

vRow and vCol each will be between -50 and 50, inclusive.

Examples

{"S.................F"}

Returns: 6

Accelerate to the right as much as you can.

{"S.................F"}

Returns: 2

You are already fast, so you need only 2 turns to finish (and you don't care that continuing with this speed would get you away from the track).

{"FX",
 "X.",
 ".X",
 "X.",
 "SX"}

Returns: 8

First you need to brake, since you are moving in the wrong direction. Then, you'll need to stop every second turn.

{"S..X",
 "X..X",
 "XX.X",
 "XXFX"}

Returns: 1

If you didn't touch the finish cell, the crash would be unavoidable. Please note that the car reaches the finish if it just touches the 'F' cell, but the car's path has to go inside the obstacle for a crash.

{"S.......X.........F"}

Returns: -1

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10709&pm=6879

Writer:

Olexiy

Testers:

PabloGilberto , brett1479 , radeye , legakis , lovro , Andrew_Lazarev

Problem categories:

Geometry, Search