Mê cung cổng dịch chuyển
Points
50
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
ds
Đề 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$
Community Discussion