Problem 2 - Grid Shortest Path (medium)

Statement. Given an h×w grid of . (free) and # (blocked). Given start cell (rs, cs) and target (rt, ct) (1-indexed). You may move up/down/left/right into free cells. Output the minimum number of moves, or -1 if impossible.

Input

h w
h lines of grid *each '.' or '#'
rs cs
rt ct

Output Single interger — min moves or -1

Constraints

• 1 ≤ h, w ≤ 1000 (but test data below is small)
• start and target are guaranteed inside grid

Sample Input:

3 3
...
...
...
1 1
3 3

Output:

4