Monument Tour

A tour operator proposes itineraries consisting of visits to $n$ monuments and museums in Paris, which is modeled as a rectangular grid. The tour operates as follows: the bus enters the city from the west (along any eastbound street) and travels eastward across the city. Whenever necessary, it may make a left or right turn to visit a monument, after which it must return to the same eastbound street it originally entered on. This process continues until the bus exits the city on the east side.

An example tour in a 6 \times 5 grid city is illustrated in the figure above. In this example, the bus enters the city at coordinate $(0,2)$ (with $(0,0)$ defined as the northwest corner of the city). It first visits the monument at $(1,2)$, which lies directly on the main road. The bus then makes a left turn to visit the monument at $(1,0)$, returns to the main road, and continues eastward. Next, it makes a right turn to visit the monument at $(2,4)$, returns again to the main road, visits the monument at $(4,2)$ (also located on the main road), and finally exits the city at coordinate $(5,2)$.

The tour operator assumes that traversing one city block costs 1 unit of gas. For the example above, the total cost is therefore 5 + 2 × 2 + 2 × 2 = 13 units of gas.

Your task is to help the tour operator determine which eastbound street the bus should follow in order to minimize the total cost of the tour while visiting all $n$ monuments.

Important Notes

• The bus is not allowed to switch to a different parallel eastbound street; it must always return to and continue along the same street it used to enter the city.

• Multiple monuments may be located at the same coordinate.