Let g be an n × n grid. you start at a particular position, 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 position x, y and already have velocity vx, vy, then at the next time step you will jump and land at position x + vx, y + vy, and you have the option of modifying each component of your velocity by ±1. at several (known) grid positions there are pits full of dragons that you want to avoid landing on. it is ok to jump over a dragon pit. you also shouldn’t jump off the grid. the goal is to arrive at a specified target position, with zero velocity, in as little time as possible. show how fast you can compute an optimal trajectory or decide that there is no way to reach the target.

hint: try this out in 1d instead of 2d. if you can solve that, you’ll be fine.