7. Ochrana pred povodňami vzorové riešenie

4 4
10
1 1
1 2
1 3
2 1
2 3
3 1
3 2
3 3
2 2
3 4

1
2
3
4
5
6
7
9
9
10

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šenia¹ 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 stenu² 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 raz³ 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]);
}