Kho báu và các cánh cửa khóa
Points
60
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
ds
Đề bài
Một hầm ngục dạng lưới $R \times C$ gồm các ô: . (trống), # (tường), S (xuất phát), X (lối ra), tối đa $6$ loại chìa khóa (a..f) và các cánh cửa tương ứng (A..F).
Bạn chỉ có thể đi qua cánh cửa A nếu trước đó đã nhặt được chìa khóa a (tương tự cho b..f). Mỗi bước đi sang ô kề cạnh mất $1$ giây.
Hãy tìm thời gian ngắn nhất để thoát ra ngoài tại X.
Dữ liệu vào
Dòng đầu chứa hai số nguyên $R, C$.
$R$ dòng tiếp theo, mỗi dòng gồm $C$ ký tự mô tả hầm ngục.
Dữ liệu ra
In ra số giây ngắn nhất để đi từ S đến X, hoặc -1 nếu không thể thoát ra.
Ví dụ
| Input | Output |
|---|---|
| 3 5 S.a.# ###A# ..X.. |
6 |
| 3 4 S#X. .a#. ..A. |
8 |
Giới hạn
- $1 \le R, C \le 100$
- Các chìa khóa thuộc
a..f, các cửa thuộcA..F
Community Discussion