Mê Cung
Nộp bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
1.0s
Python 3
5.0s
Giới hạn bộ nhớ:
256M
Đầu vào:
stdin
Đầu ra:
stdout
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C++, Go, Java, Kotlin, Pascal, Python, Scratch
Cho mê cung ô. Mỗi ô là tường (#) hoặc lối đi (.), với đúng một ô bắt đầu (A) và một ô kết thúc (B). Tìm đường đi ngắn nhất từ A đến B, chỉ được di chuyển theo bốn hướng (trên, dưới, trái, phải).
Dữ liệu vào
- Dòng 1: hai số nguyên và .
- dòng tiếp theo: mỗi dòng gồm ký tự (
#,.,A,B).
Dữ liệu ra
- Nếu tồn tại đường đi: in
YES, sau đó in độ dài đường đi, rồi in chuỗi các bước di chuyển gồm các ký tựL(trái),R(phải),U(lên),D(xuống). - Nếu không có đường đi: in
NO.
Ràng buộc
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 5 8 ######## #.A#...# #.##.#B# #......# ######## |
YES 9 LDDRRRRRU |
Đường đi ngắn nhất từ A đến B có 9 bước. |
| 3 3 A.. ### ..B |
NO | Không có đường đi từ A đến B. |
Bình luận