trang chủ / đề bài / icpc21_mt_k

Đ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 h×w, 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 t 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 t cho phép.

Mỗi đơn vị thời gian, xe di chuyển đúng 1 ô 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 t 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 3 số tự nhiên h, w và t (1≤h×w≤100, 1≤t≤109).
  • h dòng tiếp theo, mỗi dòng chứa w 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 109+7.

Ràng buộc

  • 1≤h×w≤100.
  • 1≤t≤109.
  • 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 4 cách.
3 3 2
RD#
U+#
#LR
7 Từ ô (1,1) có 1 cách: RD. Từ ô (1,2) có 3 cách: DU, DL, DR. Từ ô (2,1) có 1 cách: UR. Từ ô (2,2) có 2 cách: UD, LU. Các ô còn lại không có cách nào. Tổng cộng 7 cách.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0