Thoát khỏi mê cung
Points
35
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
graph
Đề bài
Cho một mê cung dạng lưới kích thước $R \times C$. Mỗi ô có thể là . (đường đi), # (tường), S (vị trí xuất phát) hoặc E (lối ra). Mỗi bước bạn có thể di chuyển sang một trong 4 ô kề cạnh (không đi vào tường #). Hãy tìm số bước ít nhất để đi từ S đến E.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên $R, C$ ($1 \le R, C \le 1000$).
- $R$ dòng tiếp theo, mỗi dòng gồm $C$ ký tự thuộc tập
{'.', '#', 'S', 'E'}. Dữ liệu đảm bảo có đúng một ôSvà một ôE.
Dữ liệu ra
- In ra số bước ít nhất từ
SđếnE, hoặc-1nếu không có đường đi.
Ví dụ
| Input | Output |
|---|---|
| 4 5 S.#.. ..#.. #...# ...E. |
6 |
| 3 3 S#. ##. ..E |
-1 |
Giới hạn
- $1 \le R, C \le 1000$.
Community Discussion