Điểm:
100 (p)
Thời gian:
1.5s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
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ặc1
, 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
Bình luận