CSES - Labyrinth | Mê cung
Xem PDF
Điểm:
1300 (p)
Thời gian:
1.0s
Bộ nhớ:
512M
Input:
bàn phím
Output:
màn hình
Cho bản đồ của một mê cung, nhiệm vụ của bạn là tìm ra một đường đi từ vị trí bắt đầu đến vị trí kết thúc. Bạn có thể đi sang trái, phải, lên trên và xuống dưới.
Input
- Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\): chiều cao và chiều rộng của bản đồ.
- \(n\) dòng tiếp theo, mỗi dòng gồm \(m\) ký tự mô tả mê cung. Mỗi ký tự là
.(sàn),#(tường),A(bắt đầu) hoặcB(kết thúc).
Output
- Đầu tiên in
YESnếu tồn tại đường đi vàNOnếu ngược lại. - Nếu có đường đi, dòng tiếp theo in độ dài của đường đi ngắn nhất. Và dòng cuối in mô tả của đường đi đó dưới dạng một xâu bao gồm các ký tự
L(trái),R(phải),U(lên) vàD(xuống). Bạn có thể in bất kỳ giải pháp hợp lệ nào.
Constraints
- \(1 \leq n, m \leq 1000\)
Example
Sample input
5 8
########
#.A#...#
#.##.#B#
#......#
########
Sample output
YES
9
LDDRRRRRU
Bình luận
ADMIN cho chúng em xin 0.5s nữa cho python với ạ
không đủ thời gian cho python 🙂
???
vì tôi gà
truy vết đường đi như nào nhỉ?
Note
Các bạn có thể để chế độ tiếng Việt để bài tự dịch sang tiếng Việt
admin sửa lại test mẫu giúp em được không ạ, đáng lẽ dòng tiếp theo nó phải xuất đường đi như trong output chứ!