Consider a computer game about racing cars in 2D. Your car is a pixel and the course is encoded as a set of valid pixels on an n n screen: youre given a 2D array where you can look up any pixel to see if its valid.

Your objective is to get from a given start position to a given end position as fast as possible.

Here are the rules: Time is measured in unit steps. As mentioned, you begin at some start position, naturally with zero velocity. At every time step you can modify your horizontal velocity by 1, or keep it the same. The same holds independently for vertical velocity. So if at a particular time you are at pixel x, y and already have velocity vx, vy, then at the next time step you will be at position x + vx, y + vy, after which each component of your velocity may change by 1 if you wish. Youre not allowed to shoot through the end position with arbitrary velocity. You must stop there to pick up your trophy. At every time step your car must be at a valid pixel, but also between steps you must not drive over invalid pixels. To help with this last part, youre given a table, T, of pixel pairs, where for each pair there is a bit letting you know if its legal to travel from one pixel to the other in a straight line. So in constant time you can you can look up any pair to see if moving directly from one to the other is ok.

Formulate this game as a graph problem and describe how to find the optimal route for any given race course. What is the time complexity of your algorithm?