Zadanie
Na obdĺžnikovom ostrove síce nebývajú povodne veľmi často, ale keď prídu, je to úplná katastrofa. Zaplavené sú lesy, lúky, námestia, domy a paneláky do výšky prvého poschodia. Takisto všade pláva množstvo odpadkov a opustených domácich zvieratiek. Obdĺžnikový ostrov sa totiž nachádza v strede obdĺžnikového jazera do ktorého vteká nie-až-tak-obdĺžniková rieka, ktorá pramení vo vzdialených trojuholníkových horách.
Pred rokom sa preto začalo s výstavbou protipovodňových ochranných múrov. Väčšina obyvateľov sa aktívne zapája a občas postaví štvorcový kúsok múru.1 Ľudia si väčšinou stavajú múry vo svojom okolí, no niektorí podnikaví jedinci ich stavajú aj tam, kde ich netreba – napríklad v oblastiach, ktoré sú už celé obohnané múrom – alebo tam, kde sú absolútne zbytočné – napríklad osamotený metrový kus múru v strede poľa. A samozrejme, aj takéto aktivity im budú preplatené.
Ministerstvo má záznamy o každom kúsku múra, ktorý bol kedy postavený a Klub skeptických publicistov by ich rád preveril. Chcú o každom kúsku múru zistiť, aký prospešný bol pre spoločnosť a objaviť prípadné škandály v tejto kauze.
Úloha
Ostrov si môžeme predstaviť ako obdĺžnik rozdelený na \(w \times h\) štvorčekov. Každý štvorček môže byť buď prázdny, alebo na ňom môže byť postavená časť protipovodňovej ochrany.
Voda dokáže tiecť ôsmimi smermi a priteká na každé políčko na okrajoch ostrova. Samozrejme, voda nevie zaplaviť políčko, na ktorom je postavená protipovodňová ochrana.
Dostanete rozmery ostrova a pozície, kde sa postupne stavajú múry. Na začiatku je ostrov prázdny. Vašou úlohou je po postavení každého kúsku múra povedať, aká plocha je chránená pred vodou.
Formát vstupu
Na prvom riadku vstupu dostanete dve celé čísla \(w\) a \(h\) (\(1 \leq w,h \leq 2\,000\)), pričom \(w\) je šírka a \(h\) výška obdĺžnikového ostrova.
Na druhom riadku je číslo \(n\) (\(1 \leq n \leq w \times h\)) – počet štvorcových kúskov protipovodňového múru, ktoré budú postavené.
Každý z nasledujúcich \(n\) riadkov obsahuje dve čísla \(x_i\) a \(y_i\) (\(1 \leq x_i \leq w\), \(1 \leq y_i \leq h\)), ktoré označujú pozíciu, na ktorú bude postavený \(i\)-ty kúsok múra.
Formát výstupu
Vypíšte \(n\) takých riadkov, že v \(i\)-tom riadku bude jedno celé číslo – plocha územia, ktoré je chránená protipovodňovým múrom po postavení \(i\)-teho kúsku. To znamená počet takých políčok, na ktoré nevie pritiecť voda.
Príklad
Input:
4 4
10
1 1
1 2
1 3
2 1
2 3
3 1
3 2
3 3
2 2
3 4
Output:
1
2
3
4
5
6
7
9
9
10
Prvých 8 kúskov múra ochráni pred povodňami územie veľkosti \(3 \times 3\). Deviaty štvorček nemá vôbec žiadny účinok, lebo políčko \((2,2)\) už bolo chránené. Desiaty kúsok neuzavrie žiadne územie a teda prispeje len svojou plochou.
Ministerstvo vodohospodárstva prepláca náklady na výstavbu.↩
Najprv si popíšeme myšlienkovo jednoduchšie riešenie, kde po pridaní každej steny prehľadáme celú mapu odznova a ukážeme si zopár vylepšení tohto riešenia. Nakoniec si ukážeme vzorové riešenie – offline – načítame celý vstup, spočítame riešenie a vypíšeme celý výstup.
Viacnásobné prehľadávanie
S využitím prehľadávanie do šírky (BFS – breadth-first-search) alebo prehľadávania do hĺbky (DFS – depth-first-search) sa dá vymyslieť jednoduché, funkčné riešenie, ktoré mohlo získať na testovači aspoň 3 body.
V takomto riešení si udržujeme mapku celého ostrova ako dvojrozmerné pole. V nej máme zaznačené, ktoré políčka sú voľné a na ktorých je múr. Postupne načítavame vstup a po pridaní každého kúska múru spustíme prehľadávanie od okrajov mapy. Označíme/navštívime tak všetky políčka zaliate vodou. Spočítame si počet zaliatych políčok \(z\) a výstup programu, počet chránených políčok, bude: \(w \cdot h - z\).
Pri každom prehľadávaní navštívime každé políčko mapy najviac raz, teda časová zložitosť jedného prehľadávania bude \(O(w \cdot h)\). Prehľadávanie púšťame po načítaní každého z \(n\) múrov, teda celková časová zložitosť bude \(O(n \cdot w \cdot h)\).
Mierne zlepšenia1 môžu byť napríklad:
- spúšťať prehľadávanie len ak sú okolo múru iné múry – len vtedy vieme uzavrieť nejakú oblasť ochranným múrom
- spúšťať prehľadávanie len ak uzavrieme súvislý komponent múrov
- spúšťať prehľadávanie od miesta, kde sme postavili múr – ak nájdeme okraj, táto časť prehľadávala územie nechránené pred vodou. Ak okraj nenájdeme, prehľadali sme územie ochránené pred vodou.
Takýmto spôsobom sa na testovači dalo získať až 5 bodov.
Vzorové riešenie
Na predošlom riešení si môžeme všimnúť, že robíme tú istú prácu stále odznova. Políčka zaliate vodou prehľadávame v každom kroku. Aby sme dosiahli lepšiu časovú zložitosť, nemôžeme si dovoliť prehľadávať celú mapu veľakrát. Chceli by sme teda vedieť použiť údaje z minulosti.
Ale ako? Keď uzavrieme múr – ochránime územie vnútri. Chceli by sme vedieť, aké je toto územie veľké. Po predošlom prehľadávaní je ale vonkajšok aj vnútro múru označené ako voda, čo nám vôbec nepomôže.
Čo ak by sme to robili odzadu? Čo ak by sme múry namiesto pridávania odoberali? Územie vonku múru môže byť označené ako VODA, územie vnútri ako CHRANENE. Ak odstránime stenu, vieme spustiť prehľadávanie na políčkach označených ako CHRANENE a spočítať, koľko políčok bolo vnútri – koľko ich bude zaliatych vodou. Nevieme teda múr stavať, ale vieme ho rýchlo búrať.
Presne toto aj urobíme. Vyriešime úlohu odzadu. Presnejšie, načítame celý vstup, vypočítame všetky riadky riešenia a vypíšeme ich v opačnom poradí, ako sme ich počítali.
Opäť budeme mať dvojrozmernú mapu a na nej bude každé políčko buď STENA, VODA alebo CHRANENE.
Všetky políčka mapy najprv nastavíme ako CHRANENE. Načítame si celý vstup a do mapy zaznačíme všetky STENY.
Pomocou jedného prehľadávania od okrajov mapy potom zaplavíme všetko územie, ktoré sa dá, VODOU. Prehľadávanie navštívi všetky zaplavené políčka, a tak prvá odpoveď (posledná vypísaná.) bude \(w \cdot h - zaplavene\).
Následne spracúvame vstup odzadu. Odstránime stenu2 a pokiaľ stena susedila s vodou, spustíme prehľadávanie z tohto miesta po políčkach CHRANENE. Zaplavíme tak všetko územie, ktoré bolo doteraz vnútri múru.
Odpoveď v každom kroku je \(w \cdot h - zaplavene\). Ak stena nesusedila s vodou, zostane odpoveď rovnaká ako v predošlom kroku, lebo veľkosť zaplaveného územia sa vtedy nezmení. Výstupy vypíšeme v opačnom poradí ako sme ich vypočítali.
V tomto algoritme každé políčko mapy navštívime prehľadávaním práve raz3 a tak je jeho časová zložitosť len \(O(w \cdot h)\).
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#define For(i,N) for(int i=0; i<N; i++)
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define VODA 0
#define CHRANENE 1
#define STENA 2
using namespace std;
typedef pair<int,int> pii;
int dx[] = {-1,0,1,-1,1,-1,0,1};
int dy[] = {-1,-1,-1,0,0,1,1,1};
int w, h, n, zaplavene=0;
vector<vector<int> > mapa;
vector<pii> steny; // vstup
vector<int> odpovede; // vystup
// z policka [x,y] rozlievame vodu do vsetkych CHRANENYCH
void bfs(int x, int y){
if(mapa[y][x] != CHRANENE)
return;
queue<int> q;
q.push(x); q.push(y);
mapa[y][x] = VODA;
zaplavene++;
while (!q.empty()){
int x = q.front(); q.pop();
int y = q.front(); q.pop();
For(i,8){
int nx = x+dx[i];
int ny = y+dy[i];
if(mapa[ny][nx] == CHRANENE){
q.push(nx); q.push(ny);
mapa[ny][nx] = VODA;
zaplavene++;
}
}
}
}
int main(){
scanf(" %d %d %d", &w, &h, &n);
mapa.resize(h+2, vector<int> (w+2, CHRANENE));
// po okrajoch mapy dame vodu
For(i, w+2) mapa[0][i] = mapa[h+1][i] = VODA;
For(i, h+2) mapa[i][0] = mapa[i][w+1] = VODA;
// nacitame zoznam stien a zaznacime vsetky do mapy
For(i,n){
int x,y;
scanf(" %d %d", &x, &y);
steny.pb(mp(x,y));
mapa[y][x] = STENA;
}
// rozlievame vodu postupne od okrajov
For(i,w){ bfs(i+1,1); bfs(i+1,h); }
For(i,h){ bfs(1,i+1); bfs(w,i+1); }
for(int i=n-1; i>=0; i--){
odpovede.pb(w*h - zaplavene);
int x = steny[i].ff;
int y = steny[i].ss;
// odstranime stenu
mapa[y][x] = CHRANENE;
// ak je aspon 1 sused voda, zalejeme vnutro komponentu
For(j,8)
if(mapa[y+dy[j]][x+dx[j]] == VODA){
bfs(x,y);
break;
}
}
for(int i=n-1; i>=0; i--)
printf("%d\n", odpovede[i]);
return 0;
}
Úloha sa dá naprogramovať aj trocha jednoduchšie, tu môžete vidieť stručnejšiu implementáciu algoritmu.
#include<cstdio>
#include<vector>
#define For(i, n) for(int i = 0; i<(n); ++i)
#define CHRANENE 0
#define VODA 1
#define STENA 2
typedef std::vector<int> vi;
int w,h,n, mokre = 0, M[2047][2047];
int dx[] = {1,1,1,0,-1,-1,-1,0};
int dy[] = {1,0,-1,-1,-1,0,1,1};
void zaplav(int x, int y) {
if (x<0 || y <0 || x>=w || y>=h) return;
if (M[x][y] != CHRANENE) return;
M[x][y] = VODA;
mokre++;
For(d, 8) zaplav(x+dx[d], y+dy[d]);
}
int main() {
scanf("%d%d%d", &w, &h, &n); w+=2; h+=2;
vi X = vi(n), Y = vi(n), A = vi(n);
For(i,n) {
scanf("%d%d", &X[i], &Y[i]);
M[X[i]][Y[i]] = STENA;
}
zaplav(0,0);
for(int i = n-1;i>=0;--i) {
A[i] = w*h-mokre;
M[X[i]][Y[i]] = CHRANENE;
For(d, 8) if (M[X[i]+dx[d]][Y[i]+dy[d]] == VODA) zaplav(X[i], Y[i]);
}
For(i, n) printf("%d\n", A[i]);
}
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ť.