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.