CSES - Grid Paths | Đường đi trên lưới

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
letangphuquy , Flower_On_Stone , SPyofgame
Dạng bài
Điểm: 1500 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Có tất cả \(88418\) đường đi trên một lưới ô vuông \(7 \times 7\) từ ô ở góc trái, bên trên xuống ô góc trái, bên dưới. Mỗi đường đi tương ứng với một xâu mô tả gồm \(48\) kí tự, bao gồm các kí tự D (xuống), U (lên), L (trái), R (phải).

Ví dụ, đường đi

tương ứng với xâu DRURRRRRDDDLUULDDDLDRRURDDLLLLLURULURRUULDLLDDDD.

Bạn được cho trước một xâu mô tả đường đi, mà trong đó có chứa cả kí tự ? (đi hướng nào cũng được). Nhiệm vụ của bạn là tính số lượng đường đi khớp với xâu mô tả này.

Input

  • Dòng đầu vào duy nhất có một xâu \(48\) ký tự gồm các ký tự ?, D, U, L và R.

Output

  • In ra một số nguyên: tổng số đường đi.

Example

Sample input

??????R??????U??????????????????????????LD????D?

Sample output

201

Bình luận