Mô tả:

Cho một mê cung hình chữ nhật được biểu diễn bằng một ma trận kích thước N x M, trong đó:

• Ô có giá trị 0 là ô trống, có thể di chuyển qua.
• Ô có giá trị 1 là ô tường, không thể di chuyển qua.

Người chơi bắt đầu tại tọa độ (x1, y1) và cần di chuyển đến tọa độ (x2, y2) bằng cách di chuyển theo 4 hướng: trên, dưới, trái, phải. Bạn cần tìm đường đi ngắn nhất từ vị trí bắt đầu đến vị trí đích trong mê cung, nếu có. Nếu không có đường đi, trả về -1.

Input:

• Dòng đầu tiên chứa hai số nguyên N và M (1 ≤ N, M ≤ 1000) — kích thước của mê cung (số hàng và số cột).
• Dòng thứ hai chứa hai số nguyên x1 và y1 — tọa độ bắt đầu (0 ≤ x1 < N, 0 ≤ y1 < M).
• Dòng thứ ba chứa hai số nguyên x2 và y2 — tọa độ kết thúc (0 ≤ x2 < N, 0 ≤ y2 < M).
• Tiếp theo là N dòng, mỗi dòng chứa M số nguyên 0 hoặc 1, biểu diễn mê cung.

Output:

• Trả về độ dài của đường đi ngắn nhất từ điểm bắt đầu đến điểm kết thúc. Nếu không có đường đi, trả về -1.

Ràng buộc:

2 ≤ N, M ≤ 1000
0 ≤ x1, y1, x2, y2 < N, M

Ví dụ:

Input 1:

5 5
0 0
4 4
0 1 0 0 0
0 1 1 1 0
0 0 0 1 0
1 1 0 0 0
0 0 0 1 0

Output 1:

8

Input 2:

7 7
0 0
6 6
0 0 0 0 0 0 0
1 1 1 1 1 1 0
1 1 1 1 1 1 0
1 1 1 1 1 1 0
1 1 1 1 1 1 0
1 1 1 1 1 1 0
0 0 0 0 0 0 0

Output 2:

12