Nước đi của quân Mã
Points
40
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
ds
Đề 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$
Community Discussion