Khám Phá Mê Cung Bằng Cảm Biến
Points
22
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Đây là bài toán mô phỏng tương tác (không tương tác trực tiếp — toàn bộ bản đồ được cho trước).
Một robot thám hiểm được thả vào mê cung kích thước $H \times W$ tại ô S và cần tìm đường tới ô T. Ô . là ô trống đi được, ô # là tường. Robot không biết trước bản đồ; nó thực hiện thuật toán tìm kiếm theo chiều rộng (BFS) như sau:
- Ban đầu chỉ có ô
Sđược phát hiện (đưa vào hàng đợi,discovered = 1). - Ở mỗi bước, robot lấy ô ở đầu hàng đợi ra để quét 4 ô lân cận theo đúng thứ tự: Lên (U), Phải (R), Xuống (D), Trái (L).
- Nếu một ô lân cận nằm trong bảng, không phải
#và chưa từng được phát hiện, robot đánh dấu đã phát hiện (discovered++) và đưa vào hàng đợi. - Ngay khi ô
Tđược phát hiện (hoặc lấy ra nếuS == T), quá trình dừng lại.
Hãy cho biết tổng số ô đã được phát hiện và khoảng cách ngắn nhất từ S đến T (nếu không đến được T, in ra số ô đã phát hiện và -1).
Dữ liệu vào
- Dòng đầu ghi hai số nguyên $H, W$ ($1 \le H, W \le 200$).
- $H$ dòng tiếp theo, mỗi dòng gồm $W$ ký tự thuộc
{'.', '#', 'S', 'T'}(đảm bảo có đúng mộtSvà mộtT).
Dữ liệu ra
- Hai số nguyên trên một dòng: tổng số ô đã phát hiện khi dừng và khoảng cách ngắn nhất từ
SđếnT(-1nếu không có đường đi).
Ví dụ
| Input | Output |
|---|---|
| 3 4 S..# .#.. ..T. |
9 4 |
Giới hạn
- $1 \le H, W \le 200$
Community Discussion