ŽUPANIJSKO NATJECANJE 2013. / Srednja škola, I. podskupina (1. i 2. razred) - 2. zadatak

Mirko je odlučio razviti mobilnu aplikaciju kojom se nada ostvariti veliki uspjeh, ali ne uspijeva riješiti jedan algoritamski problem i potrebna mu je vaša pomoć.

U Mirkovoj aplikaciji igrač dobije mrežu kvadratića dimenzija N redaka i N stupaca koji su na početku svi bijele boje. Potom on odigra najviše tri poteza.

U svakom potezu igrač izabere kvadratno područje unutar zadane mreže (rubovi kvadratnog područja se poklapaju sa rubovima kvadratića) i promijeni boju svih kvadratića unutar izabranog područja (kvadratići crne boje postanu bijeli, a kvadratići bijele boje crni).

Napišite program koji za zadanu konačnu mrežu kvadratića odreĎuje najmanji mogući broj poteza da se ona dobije opisanim postupkom, te pronalazi same poteze tj. kvadratna područja.

Ulazni podaci će biti takvi da je moguće dobiti zadanu konačnu mrežu; i to s najmanje jednim, a najviše tri poteza.

Ukoliko postoji više različitih načina da se dobije zadana mreža s minimalnim brojem poteza, potrebno je naći i ispisati bilo koje rješenje.

Ulazni podaci

U prvom retku ulaza nalazi se prirodan broj N (1 ≤ N ≤ 8), dimenzija mreže.

U svakom od sljedećih N redaka nalazi se niz od točno N znakova, koji predstavljaju boje kvadratića u odgovarajućem retku mreže.

Znak '.' (točka) označava bijelu boju, dok znak '#' (ljestve) označava crnu boju.

Izlazni podaci

U prvom retku izlaza potrebno je ispisati traženi minimalni broj poteza D pomoću kojega je moguće dobiti zadanu mrežu.

U sljedećih D redaka potrebno je opisati kvadratna područja u odgovarajućem potezu.

Pojedino kvadratno područje se opisuje s tri broja odvojena jednim razmakom:

<redak gornjeg lijevog kuta> <stupac gornjeg lijevog kuta> <duljina stranice>

Pritom su redci označeni brojevima 1 do N, odozgo prema dolje, a stupci brojevima od 1 do N s lijeva na desno.

Barem jedan kvadratić će biti obojan crnom bojom.

Primjeri test podataka

Ulaz

5
#####
#####
#..##
#..##
#####

Izlaz

2
1 1 5
3 2 2

Ulaz

8
........
........
.##.....
.##.....
........
....#...
........
........

Izlaz

2
3 2 2
6 5 1

Ulaz

8
........
........
.#####..
#..#..##
#..#..##
#..#..##
#..#..##
...#####

Izlaz

3
4 4 5
3 2 5
4 1 4