Đua xe trong mê cung
Đề bài
Mô tả
Ai từng học môn Trí tuệ nhân tạo do thầy Phạm Minh Tuấn giảng dạy tại Khoa Công nghệ Thông tin, Trường Đại học Bách khoa, Đại học Đà Nẵng vài năm trước đều biết rằng lập trình đua xe trong mê cung là hoạt động bắt buộc nếu muốn qua môn với điểm cao. Người tham gia được cho một mê cung là bản đồ kích thước , mỗi ô được ký hiệu bởi một trong các ký tự sau:
- #: ô chướng ngại vật.
- +: từ ô này, xe có thể di chuyển sang một ô kề cạnh (trái, phải, lên, xuống).
- L: từ ô này, xe chỉ có thể di chuyển sang trái.
- R: từ ô này, xe chỉ có thể di chuyển sang phải.
- U: từ ô này, xe chỉ có thể di chuyển lên trên.
- D: từ ô này, xe chỉ có thể di chuyển xuống dưới.
Người tham gia phải lập trình điều khiển xe sao cho từ một vị trí bất kỳ, xe đi tới một vị trí bí mật trong thời gian cho trước. Tuy nhiên, vì vị trí bí mật là bí mật nên không ai biết lập trình thế nào cho đúng: xe của người tham gia chạy lung tung cho tới khi hết giờ thì dừng lại. Thầy Tuấn muốn biết có bao nhiêu cách di chuyển hợp lệ trong toàn bộ thời gian cho phép.
Mỗi đơn vị thời gian, xe di chuyển đúng ô theo ký hiệu của ô đang đứng trên bản đồ. Xe có thể xuất phát từ bất kỳ ô nào không phải chướng ngại vật. Một cách di chuyển gồm ô xuất phát và dãy bước đi. Xe đâm vào chướng ngại vật hoặc đi ra ngoài bản đồ là không hợp lệ và cách di chuyển đó không được tính.
Dữ liệu vào
- Dòng đầu tiên chứa số tự nhiên , và (, ).
- dòng tiếp theo, mỗi dòng chứa ký tự mô tả mê cung.
Dữ liệu ra
In ra số cách di chuyển hợp lệ. Vì kết quả có thể rất lớn, hãy in ra phần dư khi chia cho .
Ràng buộc
- .
- .
- Mỗi ký tự của mê cung là một trong #, +, L, R, U, D.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 2 2 10 RD UL |
4 | Từ mỗi ô có đúng một cách di chuyển hợp lệ (đi vòng quanh), tổng cộng cách. |
| 3 3 2 RD# U+# #LR |
7 | Từ ô có cách: RD. Từ ô có cách: DU, DL, DR. Từ ô có cách: UR. Từ ô có cách: UD, LU. Các ô còn lại không có cách nào. Tổng cộng cách. |
Bình luận