Zadanie
Krajské Mesto Pravičiarov (KMP) čelí architektonickej výzve. Z dlhodobých pozorovaní obyvatelia zistili, že počas roka sa vyskytujú, čím ďalej, tým výraznejšie extrémy, čo sa týka množstva pitnej vody v ich oblasti. Niekedy majú pitnej vody veeeľmi veľa a inokedy veeeľmi málo. Preto prišli s nápadom, že potrebujú zväčšiť mestskú nádrž na vodu, aby počas priaznivejšieho obdobia dokázali uskladniť prebytočnú vodu na horšie časy.
Nádrž sa nachádza v podzemí mesta tvoreného skalami1. Ich podzemie je tiež zaujímavé tým, že skaly je možné odstraňovať (pri pohľade z hora) iba po štvorcových kusoch s rozmermi \(1m \cdot 1m\). Nádrž je tvorená iba súvislým voľným priestorom medzi skalami. Skaly sú vodotesné a teda cez ne nepresakuje voda.
Jeden by si povedal, že tu o nič nejde. Stačí bezhlavo vykopať väčšiu dieru. No ako to už v takýchto KSP úlohách býva, je tu háčik - v podzemí sa nachádzajú aj viaceré menšie nádrže na dezinfekciu, ktoré boli vytvorené iba nedávno. Problém je teda v tom, že obyvatelia neobľubujú konzumáciu dezinfekčných prostriedkov. Preto je pri plánovaní rozšírenia nádrže potrebné dbať na to, aby sa dezinfkecia nezmiešala s pitnou vodou.
Analytici z KMP zistili, že je potrebné, aby bola plocha nádrže zväčšená aspoň na \(s\) metrov štvorcovích. V úlohe projektovania nových stavebných úprav si však až tak neveria. Preto ste tu vy. Pomôžte obyvateľom KMP vyriešiť tento problém!
Úloha
Poznáme pôdorys podzemia - 2D štvorčeková mriežka, kde jeden štvorček má rozmery \(1m \cdot 1m\). Odstráňte z neho najmenší možný počet skál tak, aby vo výslednom pôdoryse zaberala nádrž na pitnú vodu aspoň \(s\) metrov štvorcovích a aby sa do nej nevylial obsah niektorej nádrže na dezinfekciu.
Každá nádrž na dezinfekciu je reprezentovaná znakom D a má rozmery presne \(1m \cdot 1m\), čiže okolo každého znaku D sa na každom z existujúcich štyroch susedných políčok nachádza skala (#).
Nádrž na pitnú vodu je tvorená políčakmi označenými znakom .. Všetky políčka nádrže na vodu tvoria práve jednu súvislú nádrž. Inými slovami, z každého políčka nádrže na pitnú vodu je možné sa dostať na každé políčko nádrže na pitnú vodu prechodom iba cez políčka nádrže na pitnú vodu.
Výsledná nádrž musí byť takisto súvislá. Obyvatelia nebudú spokojní s riešením, ktoré zapríčiní existenciu viac ako jednej nádrže na pitnú vodu v podzemí ich KMP.
Vypíšte mapu podzemia, ktoré spĺňa zadané požiadavky!
Formát vstupu
Na prvom riadku vstupu sa nachádzajú 3 čísla. Rozmery mapy podzemia - počet riadkov \(m\) a počet stĺpcov \(n\) - a požadovaná plocha nádrže \(s\). Platí, že \(1 \leq m, n \leq 1\,000\) a \(1 \leq s \leq m \cdot n\). Nasleduje \(m\) riadkov po \(n\) znakov reprezentujúcich mapu. Môžu sa tu vyskytovať iba znaky . (nádrž na pitnú vodu), # (skala) a D (dezinfekcia).
Formát výstupu
Na výstup vypíšte mapu, ktorá vznikla splnením úlohy! Vypíšte ju v rovnakom formáte, v akom bola na vstupe - \(m\) riadkov po \(n\) znakov!
Pre jeden vstup môže existovať viacero správnych riešení. V takom prípade vypíšte ľubovoľné z nich!
Môžete počítať s tým, že pre každý testovací vstup existuje riešenie.
Príklady
Input:
6 6 10
###.##
#D#..#
###..#
##..##
##.###
######Output:
##..##
#D#..#
##...#
##..##
##.###
######Jedným riešením je odstránenie skál v rohoch okolo D. (Ak sa skaly dotýkajú hranami, spojenie je stále vodotesné a obyvatelia nebudú otrávení.)
Input:
6 6 20
###.##
#D#..#
###..#
##..##
##.#D#
######Output:
##....
#D#...
.#....
....#.
...#D#
######Napriek tomu je podložie mesta stabilné. Áno, je to divné, ale funguje to, tak sa do toho nestarajme.↩︎
Ak si to zhrnieme, v úlohe nám ide o to, aby sme odstraňovali skaly, ktoré susedia s nádržou, kým nádrž nezaberá aspoň požadovanú plochu. Komplikácie s dezinfkeciou vieme jednoducho vyriešiť tak, že skaly susediace s nejakou dezinfekciou si označíme ako zakázané políčka, s ktorými nemôžeme nič robiť. Tým pádom sa nám neskôr nemôže stať, že by sme vypustili dezinfkeciu do pitnej vody.
Pomalé riešenie
Ako teda odstraňovať skaly? Ako zistiť, ktoré skaly môžeme odstraňovať? V podzemí sa má nachádzať práve jedna súvislá nádrž. To znamená, že každá skala, ktorej odstránením zväčšíme nádrž, sa musí nachádzať hneď vedľa niektorého políčka nádrže.
Prvoplánovým riešením by mohlo byť niečo také, že by sme dookola prehľadávali všetky políčka mapy a pri každom políčku skaly by sme zisťovali, či sa nachádza vedľa nádrže, a v pozitívnom prípade by sme skalu odstránili. To by sme mohli opakovať, kým by nádrž nenabudla dostatočné rozmery.
Toto riešenie by určite fungovalo, keďže vždy by sme pridávali iba políčka susediace s nádržou a postup by sme opakovali až kým by sme nedostali dostatočne veľkú nádrž.
V najhoršom prípade by sme pri požadovanej ploche \(s\) museli \(s\)-krát prehľadať celú mapu o veǩosti \(mn\). Z toho nám vychádza časova zložitosť \(O(smn)\).
Čo sa týka pamäte, vystačili by sme si s pamätaním si iba políčok mapy, čo nám dáva \(O(mn)\).
Vzorové riešenie
Zrejme tušíte, že opakované prehľadávanie celej mapy neznie ako správna cesta. Skaly na odstránenie potrebujeme “hľadať” o čosi sofistikovanejšie. Pripomínam, že nádrž musí byť práve jedna, čo vieme do reči informatiky preložiť aj ako “všetky políčka nádrže musia tvoriť jeden súvislý graf”. Súvislý graf je graf, ktorý sa skladá z práve jedného komponentu, čiže medzi ľubovoľnými dvoma vrcholmi v ňom existuje cesta.
Hm… Keby sme si existujúcu nádrž predstavili ako jeden podgraf, tak všetci jeho susedia by boli skaly, ktoré môžeme odstrániť v danom momente. Ak odstránime takúto susednú skalu, daný vrchol splynie s nádržou a teraz jeho susedia sú susedmi celej nádrže (podgrafu). A tak ďalej by sme pridávali postupne po jednej susednej skale, až kým nemáme dostatočnú nádrž.
Tu vieme teraz použiť prehľadávanie do hĺbky (DFS), alebo do šírky (BFS). Povedzme, že už máme spočítanú veľkosť pôvodnej nádrže. Môžeme začať prehľadávať mapu (graf) od ľubovoľného políčka existujúcej nádrže. Ak počas prehľadávania vidíme políčko nádrže, sme šťastní. Ak nájdeme políčko skaly (ktorá nie je blokovaná kvôli dezinfekcii), môžeme ju odstrániť a tým zväčšiť nádrž o toto jedno políčko. Keď už máme nádrž dostatočnej veľkosti, skončíme prehľadávanie.
Prečo políčka existujúcej nádrže nerátame? Tieto si musíme zrátať ešte pred prehľadávaním. Ak by sme nevedeli, aká veľka bola pôvodná nádrž, nevedeli by sme, o koľko ju potrebujeme zväčšiť. Potom by sa mohlo stať, že počas prehľadávania by sme prehľadali priveľa skál ešte predtým, než by sme prehľadali existujúcu nádrž, čím by sme vytvorili zbytočne veľkú nádrž.
Toto riešenie bude fungovať, pretože každá odstránená skala určite susedila s nádržou, čiže nemôže vzniknúť druhá nádrž, a okolo dezinfekcie máme označené zakázané políčka, čiže sa nám ani nemôže stať, že otrávime obyvyteľov KMP. Tiež určite nebude priveľká, ako už bolo objasnené v predchádzajúcom odseku.
Časová zložitosť BFS je \(O(V + E)\), kde \(V\) je počet vrcholov grafu a \(E\) je počet jeho hrán. V našom prípade je \(V\) počet políčok na mape \(mn\) a \(E \leq 4V\), pretože každý vrchol má v štvorčekovej mape nanajvýš štyroch susedov. To nám dáva časovú zložitosť \(O(mn)\).
Pri pamäťovej zložitosti sa nám nič zásadné nezmenilo. Záleží od implementácie, ale vo všeobecnosti použijeme iba zanedbateľné množstvo pamäte pre BFS/DFS. Takže čo sa týka pamäte, zostávame na \(O(nm)\), keďže si pamätáme celú mapu.
Diskusia
Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.
Pre pridávanie komentárov sa musíš prihlásiť.