Županijsko natjecanje iz informatike 2021. / Druga podskupina (3. i 4. razred) - 1. zadatak

Ana i Marija počele su slagati puzzle, svaka svoju slagalicu (sliku) dimenzija n × n.

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

Svaki dio sastoji se od određenog broja kvadratnih puzzli koje su međusobno povezane.

Puzzle koje sačinjavaju jednu i drugu slagalicu jednake su veličine.

Kad je Ana otišla spavati, Marija se odlučila s njom našaliti i prekriti njezin dio slagalice A svojim dijelom slagalice B.

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

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

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

Ulazni podaci

U prvom je retku broj n (1 ≤ n ≤ 10) iz teksta zadatka.

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 Marija povezala.

(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 dio B.)

Izlazni podaci

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

Primjer zadatka

Ulaz

3
.#.
##.
...
##.
#..
...

Izlaz

0

Objašnjenje

Pojašnjenje prvog probnog primjera: Dijelovi A i B zapravo su posve jednakog oblika te ih je moguće savršeno preklopiti.

Ulaz

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

Izlaz

1

Objašnjenje

Pojašnjenje drugog probnog primjera: Kako god B bio položen na A, barem jedna puzzla dijela A ostat će nepokrivena.

Ulaz

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

Izlaz

1

Objašnjenje

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