Kho báu và các cánh cửa khóa

General
Points
60
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
ds
Submissions
Đề 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ộc A..F
Draft saved