Mê cung chìa khóa và cánh cửa

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