Mê Cung Cổng Dịch Chuyển 0-1

Buổi 41 — SPFA & Bellman-Ford
Points
95
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
graph
Submissions
Đề 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ột S và một T).
Dữ liệu ra
  • Một số nguyên duy nhất là thời gian ngắn nhất để đi từ S đến T, hoặc -1 nế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
Draft saved