1. Tuším sme už raz ochraňovali pred povodňami vzorové riešenie

4 4
10
1 1
0 3
3 1
1 2
6 7
6 4
5 4
4 4
11 11
10 13

1
2
3
4
5
6
7
9
9
10

V tejto úlohe nám pomôže to, čo ste viacerí skúšali už pri riešení pôvodnej KSP úlohy Ochrana pred povodňami – prehľadávanie, pričom sa pomocou union-findu snažíme detekovať, kedy sme uzavreli nejaké väčšie územie a kedy nie. Pri stavaní väčšiny múrov sa totiž zväčší chránená plocha len o 1, prípadne o 0, ak ho postavíme v už chránenom území.

Predstavme si, že kúsky múra sú vrcholy grafu spojené hranami s okolitými najviac 4 kúskami múra. Môžeme si pamätať súvislé komponenty múrov a vieme, že nejakú väčšiu plochu ochránime len vtedy, keď okolo nej uzavrieme múr – keď spojíme jeden múrový komponent sám so sebou. Zisťovanie, v akom súvislom komponente je políčko, a spájanie dvoch komponentov v čase (dokonca menšom ako) \(O(\log n)\) vieme implementovať štruktúrou union-find.

Keď uzavrieme oblasť, stačí nám spustiť prehľadávanie z políčka, na ktoré sme práve pridali múr. Toto prehľadávanie musí zistiť, ktorými smermi sa z tohto políčka dá dostať na kraj (teda sú vonku/nechránené) a ktrorými smermi zostaneme vovnútri chránenej oblasti. Následne stačí označiť vnútro oblasti ako ochránené. Ako ale zistiť, čo je vonku a čo vnútri?

Pridaním ľubovoľného kúska múru vieme rozdeliť plochu na 1-4 územia. To, na koľko území plochu rozdelíme však vieme zistiť len z údajov o tom, v ktorých komponentoch súvislosti sú múry na susedných 8 políčkach.

. . .  2 2 2  . 1 .  . 1 .
1 X 1  . X .  3 X 4  1 X 1
. . .  1 1 1  . 2 .  . 1 .

Vo vyššie uvedených príkladoch reprezentuje . prázdne políčko a 1-4 políčka, na ktorých sú múry, pričom tieto múry patria do komponentov 1-4. Pridaním múra na políčko X rozdelíme plochu na 2, 1 (teda nič nerozelíme), 1 a 4 územia. Zistiť počet rôznych území (a pre každé územie prázdne políčka, ktoré sú jeho súčasťou) vám prenechávame ako implementačnú výzvu. Neodporúčame hardcodovať všetky možnosti.

Vieme teda, na koľko území je rozdelené okolie políčka X. Niektoré z území budú vnútorné a niektoré vonkajšie. Pokiaľ sme múr nepostavili v už ochránenej ploche, vdžy bude aspoň jedno územie vonkajšie (dokážte!). Pokiaľ všetku vodu okolo ostrova pokladáme za jednu oblasť, vždy bude dokonca práve jedno z oddelených území vonkajšie (dokážte!) a 0-3 vnútorné – ochránené.

Ak by sme pustili prehľadávania postupne do všetkých plôch, mohlo by sa nám stať, že na vodu narazíme, až keď prehľadáme väčšinu mapy. Ak by sme ale pustili prehľadávania paralelne …

Nech plochu rozdelíme na 2 územia. Pustíme 2 prehľadávania, do každého územia jedno. Prehľadávať budeme tak, že vždy preskúmame jedno políčko v jednom území a jedno v druhom. V každom čase budeme mať teda prehľadané rovnako veľké časti oboch území. Zastaneme, keď narazíme na vodu – vtedy stačí prehľadať druhé územie, alebo keď vyplníme nejakú celú oblasť – vtedy už nemusíme prehľadávať druhé územie, lebo vieme, že je vonkajšie.

Ak sme postavením múra ochránili oblasť veľkosti \(s\), prehľadáme tak najviac \(2s\) políčok. Úvahy sa dajú zovšeobecniť aj pre prípady, keď rozdelíme plochu na viac oblastí (spúšťame najviac 4 paralelné prehľadávania do najviac 4 území a každé prehľadávanie zastavíme, ak sme v ňom narazili na vodu alebo ak sme už vyplnili všetky ostatné územia). Rozmyslite si, že ak pridaním múra plochu rozdelíme iba na \(1\) oblasť, tak si nemôžeme dovoliť púšťať prehľadávanie. To ale nevadí, nakoľko táto jediná oblasť musí byť vonkajšia.

Každé políčko označíme najviac raz ako ochránené – počas nejakého prehľadávania. Celkovo teda prehľadáme najviac \(2 \cdot w \cdot h\) políčok. Naše online riešenie má teda celkovú časovú zložitosť \(O(w \cdot h + q)\).