Khám Phá Mê Cung Bằng Cảm Biến

Buổi 63 — Interactive & Constructive
Points
22
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề 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ếu S == 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ột S và một T).
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 đến T (-1 nế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$
Draft saved