Robot dọn nhà
Đề bài
Mô tả
Minh vừa mua một con robot dọn nhà. Sàn nhà của Minh có thể xem là một lưới vuông kích thước , chia thành các ô . Mỗi ô được ký hiệu bởi tọa độ , trong đó và là các số nguyên với và . Ban đầu, Minh đặt robot ở ô , chính giữa sàn nhà.
Robot được lập trình sẵn bằng một xâu gồm ký tự, mỗi ký tự là U, D, L hoặc R. Ở bước thứ , robot di chuyển từ ô hiện tại như sau:
- Nếu
U, robot đi tới ô . - Nếu
D, robot đi tới ô . - Nếu
L, robot đi tới ô . - Nếu
R, robot đi tới ô .
Sau một lần chạy thử, Minh thấy robot thăm chưa đủ nhiều ô khác nhau nên muốn lập trình lại nó. Tuy nhiên robot rất phức tạp, Minh chỉ có thể chèn một xâu gồm không quá ký tự (cũng gồm các ký tự U, D, L, R) vào một vị trí nào đó của xâu .
Tìm cách tối ưu hóa ra quá khó, nên Minh quyết định thử một số phương án. Có phương án. Ở phương án thứ , Minh chèn xâu ngay sau ký tự thứ của (nếu thì được chèn trước ký tự đầu tiên của ). Với mỗi phương án, Minh muốn biết số ô khác nhau mà robot thăm, tính cả ô xuất phát .
Lưu ý các phương án là độc lập: mỗi phương án chèn vào xâu ban đầu.
Dữ liệu vào
Dòng đầu tiên chứa hai số nguyên và (), độ dài xâu và số phương án.
Dòng thứ hai chứa xâu gồm ký tự, mỗi ký tự là U, D, L hoặc R.
Dòng thứ trong dòng tiếp theo chứa một số nguyên () và một xâu () gồm các ký tự U, D, L và R, mô tả phương án thứ .
Dữ liệu ra
Với mỗi phương án, in ra số ô khác nhau mà robot thăm, mỗi số trên một dòng.
Ràng buộc
- .
- chỉ gồm các ký tự
U,D,L,R. - ; , chỉ gồm các ký tự
U,D,L,R.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 5 4 RRULL 0 L 2 DDL 3 RD 5 UUU |
6 9 6 9 |
Phương án 1 cho xâu LRRULL, robot đi qua : ô khác nhau. Phương án 2 cho xâu RRDDLULL, robot đi qua : ô khác nhau. |
| 4 3 URDL 1 LLRR 4 DU 2 RRRD |
6 5 9 |
Ví dụ bổ sung (không có trong đề gốc). Phương án 1: xâu ULLRRRDL, robot quay lại và nên chỉ có ô. Phương án 2: xâu URDLDU, ô mới duy nhất là . Phương án 3: xâu URRRRDDL, phần sau của bị dịch đi . |
Bình luận