Nước đi của quân Mã

General
Points
40
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
ds
Submissions
Đề bài

Trên một bàn cờ kích thước $R \times C$ (các hàng đánh số $1..R$, các cột đánh số $1..C$), một số ô bị đặt chướng ngại vật # mà quân Mã không thể đáp xuống (nhưng vẫn có thể nhảy qua theo luật cờ vua).

Hãy tìm số bước nhảy ít nhất để quân Mã đi từ ô $(r_1, c_1)$ đến ô $(r_2, c_2)$.

Dữ liệu vào

Dòng đầu chứa hai số nguyên $R, C$.

Dòng thứ hai chứa bốn số nguyên $r_1, c_1, r_2, c_2$.

$R$ dòng tiếp theo, mỗi dòng gồm $C$ ký tự . (ô trống) hoặc # (chướng ngại vật).

Dữ liệu ra

In ra số bước nhảy tối thiểu, hoặc -1 nếu quân Mã không thể tới đích.

Ví dụ
Input Output
4 4
1 1 4 4
....
.##.
....
....
2
3 3
1 1 2 2
...
...
...
-1
Giới hạn
  • $1 \le R, C \le 500$
  • $1 \le r_1, r_2 \le R$, $1 \le c_1, c_2 \le C$
Draft saved