Minimum Moves for Robot Meeting

Two robots are placed on an M×N grid that may contain obstacles. The grid is represented as M strings of length N, where a . denotes an empty cell and a # denotes an obstacle.

The robots start at positions \((x_1, y_1)\) and \((x_2, y_2)\) respectively, and they can move up, down, left, or right to adjacent cells (no diagonal moves). A move can only be made if the target cell is within the grid and is not blocked by an obstacle.

Both robots perform a breadth-first search (BFS) to determine the set of reachable cells. They can only meet at a cell which is reachable by both. For any meeting cell \((m_x, m_y)\), the cost for the robots to get there is defined as the sum of the Manhattan distances from their starting positions:

$$d((x_1,y_1),(m_x,m_y)) + d((x_2,y_2),(m_x,m_y)) = |x_1-m_x| + |y_1-m_y| + |x_2-m_x| + |y_2-m_y|.$$

Your task is to determine the minimum possible cost among all meeting points. If no meeting point exists, output \(-1\).

Note: Although the Manhattan distance is used to compute the cost for each meeting point, a cell is considered only if it is reachable from both starting positions (taking obstacles into account).

inputFormat

The first line contains six integers: M N x1 y1 x2 y2 where

• M and N represent the number of rows and columns of the grid respectively.
• x1, y1 are the starting coordinates of the first robot.
• x2, y2 are the starting coordinates of the second robot.

The following M lines each contain a string of N characters representing the grid. A . represents an empty cell and a # represents an obstacle.

Input is provided via STDIN.

outputFormat

Output a single integer which is the minimum sum of the Manhattan distances for both robots to meet at a common reachable cell. If it is impossible for the robots to meet, print -1.

Output should be printed to STDOUT.

## sample

5 5 0 0 4 4
.....
.#...
.###.
.###.
.....

8