題目：迷宮會合

題目描述

有一個 n×m 的迷宮，由兩種格子組成：

• '.' 表示可以通行的空地
• '#' 表示障礙物，不能通過

兩個探險家 A 和 B 同時從不同位置出發：

• A 從 (x1, y1) 出發，目標是到達 (xn, yn)
• B 從 (x2, y2) 出發，目標是到達 (xm, ym)

他們每秒可以向上、下、左、右移動一格（不能斜向移動，不能走出邊界，不能進入障礙物）。

當兩人在同一時間到達同一個格子時，他們可以會合。

請計算兩人會合所需的最少時間。如果不能會合，輸出 -1。

輸入格式

第一行兩個整數 n, m（2 ≤ n, m ≤ 1000）

接下來 n 行，每行 m 個字符，表示迷宮地圖

接下來四行，每行兩個整數：

• 第一行：x1 y1（A的起點，1 ≤ x1 ≤ n, 1 ≤ y1 ≤ m）
• 第二行：x2 y2（B的起點，1 ≤ x2 ≤ n, 1 ≤ y2 ≤ m）
• 第三行：xn yn（A的目標，1 ≤ xn ≤ n, 1 ≤ yn ≤ m）
• 第四行：xm ym（B的目標，1 ≤ xm ≤ n, 1 ≤ ym ≤ m）

保證起點和目標位置都是空地 '.'。

輸出格式

一個整數，表示最少會合時間。如果不能會合，輸出 -1。

輸入範例 1

5 5
.....
.###.
.....
.###.
.....
1 1
5 5
5 1
1 5

輸出範例 1

8

輸入範例 2

4 4
....
.##.
.##.
....
1 1
4 4
4 1
1 4

輸出範例 2

-1

數據範圍

• 30% 數據：n, m ≤ 50
• 60% 數據：n, m ≤ 200
• 100% 數據：n, m ≤ 1000