Mê cung chìa khóa và cánh cửa
Points
75
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
graph
Đề bài
Cho một bản đồ mê cung kích thước $R \times C$ gồm các ký tự:
.: ô trống có thể đi qua.#: tường không thể đi qua.S: vị trí xuất phát.E: lối ra.a..d: chìa khóa loại tương ứng (tối đa 4 loại).A..D: cánh cửa bị khóa, chỉ đi qua được nếu đã nhặt chìa khóa thường tương ứng (amởA,bmởB, ...).
Mỗi bước có thể di chuyển 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 hai số nguyên $R, C$ ($1 \le R, C \le 100$).
- $R$ dòng tiếp theo, mỗi dòng gồm $C$ ký tự mô tả mê cung.
Dữ liệu ra
- In ra số bước ít nhất từ
SđếnE, hoặc-1nếu không thể thoát ra.
Ví dụ
| Input | Output |
|---|---|
| 3 5 S.a.# ###A# ...E. |
5 |
| 2 4 S#AE a#.. |
-1 |
Giới hạn
- $1 \le R, C \le 100$, số lượng loại chìa khóa tối đa là 4 (
a..d).
Community Discussion