Ovi este un băiat căruia îi place să rezolve rebus.
Un rebus poate fi privit ca o matrice de caractere cu L linii şi C coloane
şi care iniţial memorează doar valorile ‘.’ şi ‘#’. Componentele marcate
cu ‘.’ semnifică spaţiu gol şi care urmează a fi completat cu litere,
iar ‘#’ este un separator. Pe oricare linie sau coloană, spaţiile dintre
două caractere ‘#’ sau spaţiile dintre marginea matricei şi un caracter
‘#’ formează o definiţie, cu condiţia ca numărul spaţiilor să fie cel
puţin 2.
În imaginea de mai sus este un rebus cu 7 linii
şi 8 coloane. Pe prima linie sunt două definiţii: prima este de două
litere, iar a doua de 5 litere. Pe linia a treia este o singură definiţie
care ocupă întreaga linie. La fel şi pe coloanele 1 şi 7. Pe ultima
coloană este tot o singură definiţie, deoarece în colţul din dreapta-jos
este un singur spaţiu, care nu poate fi considerat definiţie. În imaginea
de mai jos sunt cinci definiţii completate, dintre care trei sunt marcate
cu ‘o’ şi două cu ‘x’.
Pentru că a rezolvat foarte multe rebusuri,
Ovi s-a plictisit deja, aşa că atunci când rezolvă unul nou, pentru
a fi mai complicat de rezolvat, el adoptă următoarea regulă: întâi scrie
o primă definiţie, oriunde în rebus, apoi completează o altă definiţie
care are proprietatea că are cel puţin o literă comună cu altă definiţie
scrisă anterior. Astfel definiţiile formează un singur grup. În exemplul
de mai sus, cele trei definiţii completate cu ‘*’ respectă regula, deci
sunt un grup, în schimb definiţiile marcate cu ‘x’ nu respectă regula,
fiecare formând câte un grup. Într-o zi, Ovi găseşte un rebus completat
parţial de cineva şi doreşte să afle câte grupuri există.
Cerinţă
Dat un rebus completat parţial, ajutaţi-l pe Ovi
să determine câte grupuri de definiţii există.
Date de intrare
Fişierul de intrare rebus.in
conţine pe prima linie două numere naturale
L şi C
separate printr-un spaţiu. Pe următoarele L
linii se găsesc câte C
caractere reprezentând fiecare linie a rebusului parţial completat. Caracterele
de pe un rând nu sunt separate prin spaţii şi pot fi:
'.' (spaţiu liber), '*'
(literă dintr-o definiţie) , '#'
(separator de definiţii).
Date de ieşire
Fişierul rebus.out
va conţine pe prima linie un singur număr natural reprezentând numărul
de grupuri de definiţii care apar în rebusul completat parţial.
Restricţii
1 <= L, C <= 100
Rebusul dat este corect, în sensul că nu
există definiţii doar parţial completate
Exemplul corespunde
celei de-a doua figuri de mai sus. Sunt 3 grupuri, primul format
din trei definiţii, iar celelalte două grupuri au fiecare câte o
definiţie.
rebus.in
rebus.out
Explicaţii
5 5
*#...
*#***
***#.
#****
...*.
3
Primul grup
este format din definţia de pe prima coloană şi cea de pe linia
a treia.
Al doilea grup este format de definiţia de pe linia a doua.
Al treilea grup este format din definiţia de pe linia a patra şi
cea de pe coloana a patra-jos.
