Băng Qua Mê Cung 0-1

Buổi 41 — SPFA & Bellman-Ford
Points
20
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
graph
Submissions
Đề 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 -1 nếu không có đường đi.
Ví dụ
Input Output
3 4
.*.
.#
.
....
0
3 3
..#
.#.
#..
-1
Giới hạn
  • 1 ≤ N, M ≤ 1000
Draft saved