Školska razina / Primjena algoritama OŠ 2023. / Osnovna škola (8. razred) - 3. zadatak

Ivan je na podu pronašao dva komadića pazli. Njegovu prijateljicu Katju zanima može li ta dva komadića spojiti tako da zajedno čine pravokutnik. Dobiveni pravokutnik ne smije sadržavati rupe. Ivanu nije dozvoljeno rotirati niti okretati pazle.

Na primjer, od komadića i može dobiti pravokutnik visine 5 cm i širine 4 cm tako da prvi komadić stavi desno od drugog: te ih spoji.

Ulazni podaci

Komadići su prikazani tablicama znakova koje sadrže ljestve i točke ('#'' i '.'). Ljestve predstavljaju kvadratni dio komadića pazle visine i širine 1 cm. Točke predstavljaju prazan dio tablice. Ljestve su u ovakvom prikazu međusobno povezane, tj. između svakog para ljestvi postoji put koji prolazi susjednim ljestvama. Dvije ljestve u tablici su susjedne ako dijele stranicu. Također, komadići ne sadržavaju rupe. U prvom retku su prirodni brojevi A i B (1 ≤ A, B ≤ 10), broj redaka i stupaca tablice koja predstavlja prvi komadić. U sljedećih A redaka nalazi se po B znakova, opis prvog komadića. U sljedećem retku su prirodni brojevi C i D (1 ≤ C, D ≤ 10), broj redaka i stupaca tablice koja predstavlja drugi komadić. U sljedećih C redaka nalazi se po D znakova, opis drugog komadića.

Izlazni podaci

U prvi redak ispiši "DA" ako Ivan može spojiti komadiće tako da zajedno čine pravokutnik, odnosno "NE" ako ne može. Ako je odgovor "DA", u drugi redak redom ispiši visinu i širinu dobivenog pravokutnika. Testni primjeri će biti takvi da će visina i širina dobivenog pravokutnika biti jedinstveni.

Bodovanje

U testnim primjerima ukupno vrijednima 20 bodova vrijedit će A = 1 i C = 1.

Primjer zadatka

Ulaz

8 6
......
......
....#.
..###.
...##.
....#.
..###.
......
6 5
.###.
.#...
.##..
.###.
.#...
.....

Izlaz

DA
5 4

Ulaz

7 6
......
######
#.....
#.####
#.##.#
#....#
######
4 6
.#####
.#....
.#..#.
.####.

Izlaz

DA
6 6

Ulaz

2 2
##
#.
2 2
#.
##

Izlaz

NE

Opis prvog probnog primjera:

Ovo su dva komadića iz teksta zadatka. Od njih Ivan može napraviti pravokutnik tako da prvog stavi na lijevu, a drugog na desnu stranu. Dobiveni pravokutnik je visine 5 cm i širine 4 cm.

Opis drugog probnog primjera:

Kako god da postavi i pokuša spojiti ove komadiće, Ivan ne može dobiti pravokutnik.