14403. Linia brzegowa [AL_05_07]

Zadanie:
https://pl.spoj.com/problems/AL_05_07

Skrócony opis problemu:

Mając macierz $n$ na $m$ będącą mapą, składającą się z lądu: 'X' i wody: '.' oblicz długość linii brzegowej wszystkich lądów i wysp. Brzegi jezior i wysp na tych jeziorach nie mają być brane pod uwagę.

Np. dla takiej macierzy 5x6:

.XXXX.
.X.XX.
XXX...
....X.
......

Wynik to 20, bo tak wygląda owa linia brzegowa (niektóre komórki liczymy więcej niż 1 raz):

..1111.
.1XXXX1
.2X.XX1
1XXX22.
.1111X1
.....1.

Rozwiązanie:

Warto oznaczyć, która woda jest tą, o którą nam chodzi (czyli odróżnić morze od jezior). Gdybyśmy zapuścili DFSa (lub BFSa) po lądach to byłoby nam trudno odróżnić do tak naprawdę jest wewnątrz, a co na zewnątrz. Łatwiej jest zatem zacząć od morza. Tak więc dla każdej komórki z brzegowych kolumn i wierszy macierzy rekurencyjnie przechodzimy w głąb macierzy oznaczając wszystkie '.' do których dojdziemy jako np. 'o'. W ten sposób po wywołaniu wszystkich tych wywołań rekurencyjnych (których będzie $2n+2m-4$) otrzymamy mapę, w której pola 'o' będą morzem, a nie jeziorami, więc pozostanie nam zliczać te przy lądzie. Zliczając idziemy od lewego górnego rogu macierzy i dla każdego lądu 'X' sprawdzamy wszystkie pola z nim są siadujące (jest ich 4). Dla każdego pola będącego 'o' inkrementujemy nasz końcowy wynik. Musimy też uwzględnić brzegi mapy, poza którymi wszędzie znajduje się morze. Tak więc dla skrajnych indeksów inkrementujemy wynik (rogi 2 razy).

Złożoność: $O(n \cdot m)$. Aby uzyskać taką złożoność musimy pamiętać w wywołaniach rekurencyjnych, żeby wchodzić tylko na pola z '.'. W przeciwnym wypadku dla mapy wypełnionej wodą będziemy przechodzić ją całą $2n+2m-4$ razy otrzymując złożoność $O(n \cdot m \cdot (n+m))$.

Ostateczny algorytm:

void go(int i, int j)
{
    tab[i][j] = 'o';
    if(j < m-1 && tab[i][j+1] == '.')
        go(i, j+1);
    if(j && tab[i][j-1] == '.')
        go(i, j-1);
    if(i < n-1 && tab[i+1][j] == '.')
        go(i+1, j);
    if(i && tab[i-1][j] == '.')
        go(i-1, j);
}

int main()
{
    char tab[5009][5009]; // dane
    int n, m; // dane
    int i, j, x;
   
    for(i = 0; i < n; ++i)
    {
        if(tab[i][0] == '.')
            go(i, 0);
        if(tab[i][m-1] == '.')
            go(i, m-1);
    }
    for(i = 1; i < m-1; ++i)
    {
        if(tab[0][i] == '.')
            go(0, i);
        if(tab[n-1][i] == '.')
            go(n-1, i);
    }
    for(i = 0; i < n; ++i)
        for(j = 0; j < m; ++j)
            if(tab[i][j] == 'X')
            {
                if(!i || tab[i-1][j] == 'o')
                    ++x;
                if(i == n-1 || tab[i+1][j] == 'o')
                    ++x;
                if(!j || tab[i][j-1] == 'o')
                    ++x;
                if(j == m-1 || tab[i][j+1] == 'o')
                    ++x;
            }
    printf("%d\n", x);
}