Phá tường vượt ngục
Points
65
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
graph
Đề bài
Nhà thám hiểm đang ở ô S trong một hầm ngục kích thước $R \times C$ và muốn đến lối ra E. Các ô . là đường đi tự do, các ô # là tường đá. Nhà thám hiểm mang theo $K$ quả bom, mỗi quả bom có thể phá hủy 1 ô tường # để đi qua. Mỗi bước chỉ có thể đi sang 4 ô kề cạnh. Hãy tìm số bước ít nhất để đi từ S đến E.
Dữ liệu vào
- Dòng đầu tiên chứa ba số nguyên $R, C, K$ ($1 \le R, C \le 500$, $0 \le K \le 10$).
- $R$ dòng tiếp theo, mỗi dòng gồm $C$ ký tự thuộc
{'.', '#', 'S', 'E'}.
Dữ liệu ra
- In ra số bước ít nhất từ
SđếnE, hoặc-1nếu không thể đến.
Ví dụ
| Input | Output |
|---|---|
| 4 4 1 S#.. .#.. .##. ...E |
6 |
| 3 3 0 S#. ### ..E |
-1 |
Giới hạn
- $1 \le R, C \le 500$, $0 \le K \le 10$.
Community Discussion