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

Dominik je napokon postao gradonačelnik. Njegova progresivna stranka Smijemo! odlučila je povezati sve gradske fontane u jedan sustav čak i ako to znači gradnju novih. Grad je moguće prikazati kao tablicu s R redaka i S stupaca, gdje polja označena s “#” označavaju ona na kojima je već izgrađena fontana dok ona označena s “.” označavaju polja kojima je uskraćena fontana. Poznato je da je dosad izgrađeno točno K fontana.

Kako stanje gradskog proračuna nije bajkovito, Dominikov financijski savjetnik Jan odlučio je obuzdati njegove snove te odabrati plan dogradnje dodatnih fontana takav da je ukupan broj fontana u gradu što manji te da one čine povezan sustav. Sustav fontana je povezan ako je moguće od svake fontane doći do svake druge krećući se samo u četiri osnovna smjera: gore, dolje, lijevo i desno te putujući samo fontanama.

Opterećeni mnogobrojnim drugim obvezama, odlučili su tebe pitati za pomoć!

Ulazni podaci

U prvom retku su prirodni brojevi R (1 ≤ R ≤ 10) i S (1 ≤ S ≤ 10), 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 ‘.’ (točka) onda je to polje prazno, u suprotnom je na polju već izgrađena fontana. U svim primjerima vrijedi da je 2 ≤ K ≤ 5.

Izlazni podaci

Potrebno je u prvom retku ispisati ukupan broj fontana. U sljedećih R redaka potrebno je ispisati po S znakova, plan izgradnje sustava fontana koji zadovoljava uvjete iz zadatka.

Probni primjeri

Ulaz

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

Izlaz

6
.###
.#..
.#..
.#..

Opis prvog probnog primjera:

U ovom primjeru dvije fontane spojene su izravno s dodatne 4 fontane. Time ukupan plan sustava sadrži 6 fontana te bi to rješenje dobilo svih 10 bodova. Za primjer, rješenje s recimo 7 fontana, dobilo bi prema zadanoj formuli 5 bodova.

Ulaz

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

Izlaz

9
..#..
..###
..#..
..#..
###..

Ulaz

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

Izlaz

11
##...
.####
.#..#
.#..#
.#...