Thoát khỏi mê cung

Buổi 18 — BFS & DFS
Points
35
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
graph
Submissions
Đề 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 ô S và một ô E.
Dữ liệu ra
  • In ra số bước ít nhất từ S đến E, hoặc -1 nế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$.
Draft saved