The traffic grid can be modeled with a graph consisting of ~2R~ vertices, one for each of two endpoints in a row. Every vertex (except the ones in the first and last rows) is connected to three other vertices – the ones above and below it, as well as the other endpoint in the same row. Knowing the shortest paths between every pair of vertices in this graph allows us to easily calculate the shortest paths in the original grid. There are four cases – we can choose to start going left or right, and to approach the destination from the left or the right.

The all-pairs shortest paths problem can be easily solved by the Floyd-Warshall algorithm in ~\mathcal O(R^3)~ complexity, enough for ~70\%~ of points.

For full points, we can implement Dijkstra's algorithm or a dynamic programming solution that takes advantage of the special properties of the graph. First note that the shortest path between the endpoints of two rows ~A~ and ~B~ may go through rows outside the interval ~[A, B]~, which introduces cycles in our state space, an obstacle when using dynamic programming. This can be solved by precalculating the shortest path from one endpoint of the row to the other. After this, we can use dynamic programming to populate the shortest paths table. The overall complexity is ~\mathcal O(R^2)~.