Minimum Cost Path on City Map

You are given a city map represented as a grid. Each cell in the grid is either a road (denoted by a dot .) or an obstacle (denoted by a hash #). A car traveling on this map obeys the following rules:

• Going straight (i.e. continuing in the same direction) does not incur any cost.
• Making a left turn costs \(1\) unit.
• Making a right turn costs \(5\) units.
• A U-turn (i.e. turning 180 degrees) is only permitted when the three moves – going straight, turning left, and turning right – are all impossible. A U-turn costs \(10\) units.

The car may move only in the four cardinal directions: north, east, south, and west. Initially, the car is located at the starting cell and you may choose any initial direction for which the adjacent cell is available (with no additional cost for the choice of direction).

Your task is to determine the minimum cost required to travel from the given starting cell to the destination cell.

inputFormat

The input begins with a line containing two integers \(n\) and \(m\) (the number of rows and columns of the city map).

This is followed by \(n\) lines, each containing a string of length \(m\). Each character is either . (a road) or # (an obstacle).

The next line contains two integers \(r_s\) and \(c_s\) denoting the starting cell coordinates (0-indexed).

The final line contains two integers \(r_t\) and \(c_t\) denoting the destination cell coordinates (0-indexed).

outputFormat

Output a single integer, the minimum total cost to reach the destination from the starting cell. If the destination is unreachable, output -1.

sample

3 3
...
...
...
0 0
2 2

1