3. Málo miesta na párty vzorové riešenie

4 6
#############
# . . | | | #
#.+-+.+.+.+.#
# | | | . . #
#-+.+-+.+-+.#
# . | . . | #
#.+-+.+.+-+.#
# . . . . . #
#############

24

#############
# . . | | | #
#.+-+.+.+.+.#
# X | | . . #
#-+.+-+.+-+.#
# . | . . | #
#.+-+.+.+-+.#
# . . . . . #
#############

Síce vstup vyzerá strašidelne, ale to vôbec nevadí, načítame ho tak ako je. Keďže budeme hľadať obsahy miestností, potrebujeme presný plán budovy. Keďže každé prázdne políčko (' ') má obsah 1, tak nám pre každú miestnosť stačí zrátať, koľko je v nej takých prázdnych políčok. Nakoniec len vezmeme dve susedné miestnosti, ktoré nám po ich spojení dajú najväčší možný obsah. Jednoduché, však? Ale poďme na to postupne.

Hor sa prvú sadu!

Keďže v prvej sade sú všetky miestnosti na jednom riadku, môžeme postupne prechádzať druhým riadkom vstupu a zaradom počítať obsahy jednotlivých miestností. Takže, spravíme si pole, kam si budeme postupne tieto obsahy ukladať a prechádzame vstup – ak narazíme na stenu ('|'), pridáme do poľa s obsahmi 0. Ak prídeme na prázdne políčko (' ') pripočítame k poslednému číslu v poli 1. Inak povedané, kým sme v \(i\)-tej miestnosti, tak k \(i\)-temu číslu v poli prirátavame 1 za každé prázdne políčko. Keď narazíme na stenu, vieme že nám skončila miestnosť a bude nasledovať ďalšia. Akurát, na začiatku nemusí byť po '#' hneď stena, takže si na začiatok musíme dať “umelo” do poľa s obsahmi 0. Nakoniec už iba prejdeme toto pole obsahov, nájdeme 2 susedné miestnosti s najväčším súčtom a tento súčet vypíšeme.

Ostatné sady

Ako vyrátať obsah miestnosti?

Na vyrátanie obsahu nejakej miestnosti nám stačí začať prehľadávanie do hĺbky (DFS) z nejakého bodu vnútri tejto miestnosti a zrátať počet políčok, cez ktoré prejdeme. Toto budeme v najhoršom prípade musieť urobiť pre každý bod v budove, teda v čase \(O(nm)\).

Pomalé riešenie

Postupne prejdeme všetkými zbúrateľnými stenami a vypočítame obsah miestnosti napravo a naľavo, resp. hore a dole, podľa toho aký typ steny sme zbúrali. (!!!POZOR, treba ošetriť prípad, v ktorom je z oboch strán steny rovnaká miestnosť. Po zbúraní takejto steny ostane obsah miestnosti nezmenený!!!) Súčet týchto obsahov je obsah misetnosti, ktorá vznikne po zbúraní tejto steny. Doterajší najväčší obsah si budeme pamätať a po preskúmaní všetkých zbúrateľných stien vypíšeme najväčší obsah miestnosti po zbúraní nejakej steny. Časová zložitosť tohoto riešenia je \(O((nm)^2)\), pretože pre každú zbúrateľnú stenu, ktorých je rádovo nm, sme rátali obsah susedných miestností, čo je rádovo taktiež \(nm\).

Pamäťová zložitosť tohoto riešenia je \(O(nm)\), pretože si potrebujeme pamätať vstup.

Optimálne riešenie

Všimnime si, že obsah nejakej miestnosti počítame toľkokrát, koľko má zbúrateľných stien, aj napriek tomu, že jej obsah sa za celý čas nezmenil.

Preto ešte predtým ako budeme iterovať zbúrateľnými stenami, si predpočítame obsahy daných miestností.

Potom, keď budeme iterovať cez všetky zbúrateľné steny, si vieme vyrátať obsah miestnosti po zbúraní steny v \(O(1)\).

Predpočítať si obsahy miestností vieme znova pomocou DFS, no skôr ako začneme, musíme ešte: - Vytvoriť pole(1), do ktorého si budeme ukladať už vypočítané obsahy miestností. - Vytvoriť 2D pole(2), ktoré bude mať rozmery ako plánik budovy. V ňom si do každého bodu zapíšeme, na ktorom indexe v poli(1) je uložený obsah miestnosti, ktorá obsahuje tento bod.

Teraz už môžeme predpočítavať. Všimnime si, že skutočne prejdeme každým bodom v plániku nanajvýš raz, nakoľko nemusíme spúšťať DFS (hľadanie obsahu) z bodov, pre ktoré už v poli(2) existuje nejaký index. Preto bude mať táto časť algoritmu časovú zložitosť \(O(nm)\).

Časová zložitosť tohoto riešenia je \(O(nm)\), pretože sme najprv predpočítali obsahy miestností v \(O(nm)\), nakoľko sme prešli celý obsah budovy, a potom pre každú zbúrateľnú stenu, ktorých je rádovo \(nm\), sme rátali obsah susdených miestností v \(O(1)\). Pamäťová zložitosť je \(O(nm)\), pretože si potrebujeme pamätať vstup (nm), pole(1) (nanajvýš nm), pole(2) (nm).

O algoritme DFS sa môžete dozvedieť viac tu: https://www.ksp.sk/kucharka/dfs/

# ulozim obsahy zistene dfs do pola group
# prejdem vsetky policka, a skusam rozbijat steny
# pozriem okolo nej a poscitavam obsahy, ak este neboli zapocitane

import sys

sys.setrecursionlimit(10**6)

n, m = map(int, input().split())
inp = [[j for j in input()] for _ in range(2 * n + 1)]

group = [[0 for _ in range(2 * m + 1)] for _ in range(2 * n + 1)]
curr_group = 1
areas = [0, 0]


def inside(i, j):
    return 0 <= i < 2 * n + 1 and 0 <= j < 2 * m + 1


def dfs(i, j):
    group[i][j] = curr_group
    areas[curr_group] += 1

    # vnor sa hlbsie, ked je to vnutri
    if inside(i + 2, j) and group[i + 2][j] == 0 and inp[i + 1][j] == ".":
        dfs(i + 2, j)
    if inside(i - 2, j) and group[i - 2][j] == 0 and inp[i - 1][j] == ".":
        dfs(i - 2, j)
    if inside(i, j + 2) and group[i][j + 2] == 0 and inp[i][j + 1] == ".":
        dfs(i, j + 2)
    if inside(i, j - 2) and group[i][j - 2] == 0 and inp[i][j - 1] == ".":
        dfs(i, j - 2)

    return


for i in range(1, 2 * n + 1, 2):
    for j in range(1, 2 * m + 1, 2):
        if inp[i][j] == " " and group[i][j] == 0:
            dfs(i, j)
            curr_group += 1
            areas.append(0)


ans = max(areas)
for i in range(1, 2 * n):
    for j in range(1, 2 * m):
        if inp[i][j] == "|":
            if group[i][j - 1] != group[i][j + 1]:
                ans = max(ans, areas[group[i][j - 1]] + areas[group[i][j + 1]])
        elif inp[i][j] == "-":
            if group[i - 1][j] != group[i + 1][j]:
                ans = max(ans, areas[group[i - 1][j]] + areas[group[i + 1][j]])

print(ans)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    cin.tie(0)->sync_with_stdio(0);

    int N, M;
    cin >> N >> M;
    cin.ignore();

    int Vn = N * M;
    vector<vector<int>> Eex(Vn), Erm(Vn);
    auto convert = [M](int x, int y) { return y * M + x; };
    for (int y = 1; y < 2 * N + 1; y += 2) {
        string labove, lcurr;
        getline(cin, labove);
        getline(cin, lcurr);
        for (int x = 1; x < 2 * M + 1; x += 2) {
            int v = convert(x / 2, y / 2);
            int vx = convert(x / 2 - 1, y / 2);
            int vy = convert(x / 2, y / 2 - 1);
            if (x > 1) {
                if (lcurr[x - 1] == '.') {
                    Eex[v].push_back(vx);
                    Eex[vx].push_back(v);
                } else {
                    Erm[v].push_back(vx);
                    Erm[vx].push_back(v);
                }
            }
            if (y > 1) {
                if (labove[x] == '.') {
                    Eex[v].push_back(vy);
                    Eex[vy].push_back(v);
                } else {
                    Erm[v].push_back(vy);
                    Erm[vy].push_back(v);
                }
            }
        }
    }

    vector<int> C(Vn, -1);
    auto dfs = [&](auto&& dfs, int v, int c) -> void {
        C[v] = c;
        for (int u : Eex[v])
            if (C[u] == -1)
                dfs(dfs, u, c);
    };
    vector<int> Sz;
    for (int v = 0; v < Vn; ++v) {
        if (C[v] == -1) {
            dfs(dfs, v, Sz.size());
            Sz.push_back(0);
        }
        ++Sz[C[v]];
    }

    int res = *max_element(Sz.begin(), Sz.end());
    for (int v = 0; v < Vn; ++v)
        for (int u : Erm[v])
            if (C[v] != C[u])
                res = max(res, Sz[C[v]] + Sz[C[u]]);

    cout << res << '\n';
}