Code Submission Evaluation System Login

Datatähti-valmennus

Ruudukko


Task | Statistics


CSES - Ruudukko

Time limit:1.00 s Memory limit:128 MB

$7 \times 7$ -ruudukossa vasemmasta yläkulmasta vasempaan alakulmaan on 88418 erilaista reittiä. Jokaista reittiä vastaa 48-merkkinen kuvaus, joka muodostuu merkeistä A (alas), Y (ylös), V (vasen) ja O (oikea).

Esimerkiksi reittiä

vastaa kuvaus AOYOOOOOAAAVYYVAAAVAOOYOAAVVVVVYOYVYOOYYVAVVAAAA.

Sinulle on annettu kuvaus, jossa osa merkeistä on ? (mikä tahansa suunta). Tehtäväsi on laskea, montako reittiä vastaa kuvausta.

Syöte

Syötteenä on reitin kuvaava merkkijono, joka muodostuu merkeistä ?, A, Y, V ja O.

Tuloste

Ohjelmasi tulee tulostaa yksi kokonaisluku: montako reittiä on olemassa.

Esimerkki

Syöte:
??????O??????Y??????????????????????????VA????A?

Tuloste:
201