Mê cung cổng dịch chuyển

General
Points
50
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
ds
Submissions
Đề bài

Một mê cung kích thước $R \times C$ gồm các ô: . (đường đi), # (tường), S (xuất phát), E (đích), và các cổng dịch chuyển được ký hiệu bằng chữ cái thường từ a đến z.

Mỗi bước mất $1$ giây, bạn có thể đi sang $4$ ô kề cạnh không phải tường. Ngoài ra, nếu đang đứng ở một ô mang ký tự chữ cái thường (ví dụ a), bạn cũng có thể dùng $1$ giây để dịch chuyển tức thời đến bất kỳ ô nào khác có cùng ký tự đó (a).

Hãy tìm thời gian ngắn nhất để đi từ S đến E.

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ả mê cung (đảm bảo có đúng một S và một E).

Dữ liệu ra

In ra số giây ngắn nhất để đi từ S đến E, hoặc -1 nếu không thể đến đích.

Ví dụ
Input Output
3 5
S.a.#
###.#
#a..E
6
3 3
S#a
###
b#E
-1
Giới hạn
  • $1 \le R, C \le 500$
Draft saved