Băng Qua Mê Cung 0-1
Points
20
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
graph
Đề bài
Bạn đang đứng ở ô (1, 1) của một mê cung kích thước N × M và cần đi đến ô (N, M). Mỗi bước bạn có thể di chuyển sang một trong 4 ô kề cạnh (lên, xuống, trái, phải). Các ô có ký tự . là đường trống (chi phí bước vào là 0), * là chướng ngại vật có thể phá hủy (chi phí bước vào là 1), và # là tường cứng không thể đi qua. Ô (1, 1) luôn là .. Hãy tìm tổng chi phí nhỏ nhất để đi từ (1, 1) đến (N, M).
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên N và M.
- N dòng tiếp theo, mỗi dòng là một xâu độ dài M chỉ gồm các ký tự
.,*,#.
Dữ liệu ra
- Một số nguyên duy nhất là chi phí nhỏ nhất tìm được, hoặc
-1nếu không có đường đi.
Ví dụ
| Input | Output |
|---|---|
| 3 4 .*. .#. .... |
0 |
| 3 3 ..# .#. #.. |
-1 |
Giới hạn
- 1 ≤ N, M ≤ 1000
Community Discussion