Dangerous Skating (Translated)

JOI Spring Training Camp 2015/16
Original Statement / Submission Site

Problem Statement

JOI-kun enjoys ice skating on a vast outdoor skating rink surrounded by nature.

The rink is represented by a rectangular grid with R rows from north to south and C columns from west to east. The cell in row r from the north and column c from the west is denoted by (r, c).

Each cell is either passable or blocked by an ice block. Every cell along the outer boundary of the rink contains an ice block, so JOI-kun cannot leave the rink by sliding outside it. In other words, cells (i, 1) and (i, C) for 1 ≤ i ≤ R, and cells (1, j) and (R, j) for 1 ≤ j ≤ C, all contain ice blocks.

JOI-kun is not very skilled at skating. To move, he pushes off from his current cell in one of the four directions: north, south, east, or west. He then continues sliding until he stops on the cell immediately before the first ice block in that direction. The entire action from pushing off until stopping counts as one move. If the adjacent cell in a direction already contains an ice block, he cannot move in that direction.

One day, JOI-kun discovers that whenever he pushes off from a cell, an ice block appears in that cell. No ice blocks appear in cells that he merely passes through while sliding.

Because continuing to skate under these conditions is extremely dangerous, JOI-kun wants to escape from the rink as quickly as possible.

JOI-kun is currently at cell (r₁, c₁). To escape, he must stop exactly on the exit cell (r₂, c₂). Merely passing over the exit while sliding does not allow him to escape.

Task

Given the initial positions of the ice blocks, JOI-kun's current position, and the exit position, determine whether JOI-kun can stop on the exit cell. If he can, compute the minimum number of moves required. Otherwise, output -1.

Input

The input is given as follows:

• The first line contains two integers R and C, representing the number of rows and columns of the rink.
• Each of the next R lines contains a string of C characters:
  • . indicates a passable cell.
  • # indicates a cell containing an ice block.
• The next line contains two integers r₁ and c₁, JOI-kun's current position.
• The final line contains two integers r₂ and c₂, the exit position.

Output

Output one integer: the minimum number of moves required for JOI-kun to stop on the exit cell. If this is impossible, output -1.

Constraints

• 3 ≤ R ≤ 1,000
• 3 ≤ C ≤ 1,000
• 1 ≤ r₁, r₂ ≤ R
• 1 ≤ c₁, c₂ ≤ C
• Every boundary cell contains an ice block.
• The starting cell and the exit cell do not contain ice blocks.

Subtasks

• Subtask 1 [13 points]: R ≤ 10, C ≤ 10, and whenever the exit is reachable, it can be reached in at most 10 moves.
• Subtask 2 [65 points]: R ≤ 200 and C ≤ 200.
• Subtask 3 [22 points]: No additional constraints.

Sample Input 1

5 5
#####
#...#
#...#
#...#
#####
2 2
3 3

Sample Output 1

4

Explanation of Sample Output 1

In the initial state, JOI-kun is at cell (2, 2), and the exit is at cell (3, 3).

First, JOI-kun moves east. The cell from which he pushed off, (2, 2), then becomes an ice block.

After that, he moves west, then south, then north. He stops on the exit after a total of 4 moves.

It is impossible to stop on the exit in 3 or fewer moves, so the answer is 4.

Sample Input 2

8 6
######
#..#.#
##...#
#....#
#.#..#
#....#
##...#
######
4 3
6 4

Sample Output 2

5

Sample Input 3

5 5
#####
#.#.#
#.#.#
#.#.#
#####
2 2
4 4

Sample Output 3

-1

Sample Input 4

3 3
###
#.#
###
2 2
2 2

Sample Output 4

0

In Sample Input 4, JOI-kun is already standing on the exit cell, so no moves are required.