Mê Cung Cổng Dịch Chuyển 0-1
Points
95
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
graph
Đề bài
Bạn đang ở ô S trong một mê cung N × M và muốn đến ô T trong thời gian ngắn nhất. Mỗi bước di chuyển sang một ô kề cạnh không phải tường # tốn 1 giây. Ngoài ra, trên lưới có các cổng dịch chuyển được đánh số từ 0 đến 9. Khi đứng tại một cổng mang số c, bạn có thể dịch chuyển tức thời (tốn 0 giây) đến bất kỳ cổng nào khác có cùng số c trên lưới.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên N và M.
- N dòng tiếp theo, mỗi dòng gồm M ký tự thuộc tập
{'.', '#', 'S', 'T', '0'..'9'}(đảm bảo có đúng mộtSvà mộtT).
Dữ liệu ra
- Một số nguyên duy nhất là thời gian ngắn nhất để đi từ
SđếnT, hoặc-1nếu không thể đến nơi.
Ví dụ
| Input | Output |
|---|---|
| 4 5 S0#.. .#... ..#0T ..... |
2 |
| 3 3 S#. ### .0T |
-1 |
Giới hạn
- 1 ≤ N, M ≤ 500
Community Discussion