Županijsko natjecanje / Osnovna škola (8. razred) 2022 - 2. zadatak

Domagoj je veliki obožavatelj i vlasnik pozamašne količine puzzli u obliku znaka za zbrajanje “+”. Jedna puzzla takvog oblika sastoji se od 5 polja, gdje središnje polje označavamo znakom “+”, gornji i donji krak znakom “|” te lijevi i desni krak znakom “-”.

Znajući za tu Domagojevu sklonost, Juraj mu je za rođendan poklonio tablicu čija su neka polja bila prazna, a neka popunjena te mu zadao zadatak: možeš li popuniti tablicu svojim puzzlama tako da su sva prazna polja popunjena te se nijedne dvije puzzle ne preklapaju. Ako je to moguće, nacrtaj mi jedan od mogućih načina.

Ulazni podaci

U prvom retku su prirodni brojevi R (1 ≤ R ≤ 1000) i S (1 ≤ S ≤ 1000), broj redaka i stupaca tablice iz zadatka. U svakom od sljedećih R redaka je po S znakova ‘.’ i ‘#’ koji predstavljaju tablicu. Ako je znak u i-tom retku i j-tom stupcu matrice ‘.’ onda je to polje prazno, u suprotnom je polje popunjeno.

Izlazni podaci

Ako nije moguće popuniti tablicu potrebno je ispisati riječ “NE”. U suprotnom potrebno je u prvi redak ispisati “DA” te u sljedećih R redaka ispisati popunjenu tablicu. Popunjena polja moraju ostati “#”, središta pluseva moraju biti označena s “+”, gornji i donji krak s “|” te lijevi i desni krak s “-”. Ako postoji više načina, potrebno je ispisati bilo koji.

Probni primjeri

Ulaz

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

Izlaz

DA
##|#
#-+-
##|#
####

Ulaz

3 3
#..
...
..#

Izlaz

NE

Ulaz

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

Izlaz

DA
#|####
-+-#|#
#||-+-
#-+-|#
##|###