Školsko natjecanje / Srednja škola (1. podskupina) 2022 - 3. zadatak

Mirko je za rođendan dobio matricu od R × S slova A, B i C. Mirko želi odabrati neka tri uzastopna retka matrice, drugim riječima, neku podmatricu dimenzija 3 × S, i popločati je trominama. Svaka tromina (dimenzija 1 × 3 ili 3 × 1) pokriva tri uzastopna slova u istom retku ili stupcu koja moraju biti sva različita – dakle, svaka tromina mora pokriti jedno slovo A, jedno B i jedno C (u bilo kojem poretku). Podmatrica se mora cijela popločati, a tromine se ne smiju preklapati ili izlaziti izvan podmatrice.

Napišite program koji će pomoći Mirku u ovom poduhvatu i odgovoriti koliko podmatrica dimenzija 3 × S, od ukupno R − 2 takvih podmatrica, ima svojstvo da ju je moguće (neovisno o ostatku matrice) popločati trominama na opisani način. Drugim riječima, na koliko načina Mirko može odabrati tri uzastopna retka matrice tako da je odabrani dio moguće popločati trominama.

Donja slika prikazuje drugi primjer niže. Jedna trojka uzastopnih redova (drugi, treći i četvrti redak) može se popločati trominama kao na slici. To isto vrijedi za još jednu podmatricu traženih dimenzija (onu koju čine treći, četvrti i peti redak) pa je izlazni podatak 2.

Ulazni podaci

U prvom su retku prirodni brojevi R i S (3 ≤ R, S ≤ 20) – dimenzije matrice, tj. broj redaka i broj stupaca.

Idućih R redaka sadrži po S znakova A, B ili C koji predstavljaju Mirkovu matricu slova.

Izlazni podaci

U jedini redak ispišite traženi broj.

Probni primjeri

Ulaz

3 6
ABCABC
BACBAC
CBACBA

Izlaz

1

Ulaz

6 7
CABCABC
ACABBAC
BCBACCA
CCABABB
ACABBAC
BBCACCB

Izlaz

2