[Buổi 11][Quay lui & Cắt tỉa][ADV] Bài 1: Đường đi phủ lưới 7×7
Đường đi phủ lưới 7×7
Bối cảnh và bài toán
Một robot phải đi từ ô góc trên trái (1,1) tới ô góc dưới trái (7,1) trong đúng 48 bước, đi qua mỗi ô của lưới 7×7 đúng một lần. Chuỗi lệnh có thể chứa hướng cố định U,D,L,R hoặc ? cho phép chọn tự do.
Yêu cầu
Đếm số đường đi khớp chuỗi lệnh và thăm mỗi ô đúng một lần.
Input
- Một dòng gồm đúng 48 ký tự thuộc
U,D,L,R,?.
Output
In số đường đi hợp lệ.
Ràng buộc
|s| = 48
Chấm điểm
| Subtask | Điểm | Điều kiện | Official tests |
|---|---|---|---|
| S1 | 20% | Có ít nhất 32 ký tự hướng cố định | 01–04 |
| S2 | 30% | Có ít nhất 16 ký tự hướng cố định | 05–10 |
| S3 | 50% | Không có ràng buộc bổ sung | 11–20 |
Ví dụ 1
Input
??????R??????U??????????????????????????LD????D?
Output
201
Giải thích. Có 201 Hamiltonian paths thỏa mẫu lệnh.
Ví dụ 2
Input
DDDDDD??????????????????????????????????????????
Output
0
Giải thích. Sau 6 bước robot đã tới đích quá sớm, không thể hoàn thành đủ 48 bước mà không thăm lại ô.
Thông tin bài tập
| Thuộc tính | Giá trị |
|---|---|
| Mã bài | DSA-M04-B11-ADV01 |
| Buổi | B11 |
| Loại bài | ADVANCED |
| Mức độ khó | Khó (Hard) |
| Thời gian làm bài khuyến nghị | 90 phút |
| Time limit | 2 giây |
| Memory limit | 256 MB |
| Tổng điểm | 100 |
| Chuẩn ngôn ngữ tham chiếu | C++11 trở lên |
| Yêu cầu bổ sung | Decision Note |
Nguồn: Phỏng theo CSES Problem Set — Grid Path Description (Task 1625).
Tham khảo: https://cses.fi/problemset/task/1625/
Comments