Županijsko natjecanje iz informatike 2021. / Prva podskupina (1. i 2. razred) - 2. zadatak

Tri djevojke: Ana, Marija i Anna-Maria počele su slagati puzzle, svaka svoju slagalicu (sliku).

Dimenzije slagalica koje slažu Ana i Marija su n × n, a dimenzije Anna-Marijine slagalice su m × m.

Do kraja dana Ana je na stolu složila dio svoje slagalice koji ćemo zvati A, Marija dio svoje slagalice koji ćemo zvati B, a Anna-Maria dio svoje slagalice koji ćemo zvati C.

Svaki dio sastoji se od određenog broja kvadratnih puzzli koje su međusobno povezane. Puzzle koje sačinjavaju jednu, drugu i treću slagalicu jednake su veličine.

Kad su Ana i Marija otišle spavati, Anna-Maria odlučila se s njima našaliti i prekriti njihove dijelove slagalice A i B svojim dijelom slagalice C.

U tu svrhu ona može i jedan i drugi i treći dio slagalice pomicati (translatirati) i rotirati po stolu (za višekratnike od 90 stupnjeva, ali ne i preokretati), i potom svoj dio C pomaknuti tako da djelomično ili potpuno prekrije dijelove A i B.

I njih može micati po volji, ali ne i preklapati, tj. dijelovi A i B neće se međusobno prekrivati.

Pomozite Anna-Mariji i napišite program koji odgovara na sljedeće pitanje: koliki je najmanji ukupan broj puzzli dijelova A i B koje će ostati vidljive ("viriti") ispod dijela slagalice C nakon pokrivanja?

(Ako je A i B moguće potpuno prekriti, odgovor je nula.)

Ulazni podaci

U prvom su retku brojevi n i m (1 ≤ n ≤ m ≤ 10) iz teksta zadatka, odvojeni razmakom.

Sljedećih n redaka sadrži po n znakova koji opisuju dio slagalice A.

Taj dio čine znakovi ljestve ("#") koji predstavljaju puzzle koje je Ana povezala. Ostatak znakova su točke (".").

Slijedi prazan redak, a nakon njega n redaka od po n znakova koji na isti način opisuju dio slagalice B, tj. puzzle koje je povezala Marija.

Slijedi prazan redak, a nakon njega m redaka od po m znakova koji na isti način opisuju dio slagalice C, tj. puzzle koje je povezala Anna-Maria.

(Dio A je povezan, tj. ne sastoji se od dvaju ili više dijelova čije puzzle nisu međusobno spojene po svojim rubovima. Isto vrijedi za dijelove B i C.)

Izlazni podaci

U prvi i jedini redak ispišite traženi broj iz teksta zadatka.

Primjer zadatka

Ulaz

2 4
#.
##
##
##
..#.
###.
.###
.#..

Izlaz

1

Objašnjenje

Pojašnjenje prvog probnog primjera: Postavimo li dio A odmah desno od dijela B bez rotiranja, možemo ih pokriti srednjim dvama redcima dijela C tako da samo donja-lijeva puzzla dijela B ostane

vidljiva.

Ulaz

4 4
#.#.
#.#.
####
...#
.###
....
....
....
####
.###
.#.#
.###

Izlaz

1

Objašnjenje

Pojašnjenje drugog probnog primjera: Dio A možemo rotirati za 180 stupnjeva, potom dio B postaviti uz njegov gornji dio, nakon čega dio C (bez rotiranja) može prekriti sve osim jedne puzzle dijela

A.

Ulaz

3 4
#..
##.
.#.
...
..#
###
##..
.##.
####
..#.

Izlaz

1

Objašnjenje

Pojašnjenje trećeg probnog primjera: Vidi sliku u tekstu zadatka.