Phá tường vượt ngục

Buổi 18 — BFS & DFS
Points
65
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
graph
Submissions
Đề 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 đến E, hoặc -1 nế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$.
Draft saved