Zadanie

Na Matfyze práve prebiehajú masívne rekonštrukcie. Za pavilónom matematiky stavajú novú budovu, v akvárkach1 vymieňajú staré drevené sedačky a ešte aj KSPáci si znovu prerobili T2ku2. No a rekonštrukcií sa samozrejme nevyhnú ani záchody.

Vedenie by potrebovalo zistiť, koľko záchodových mís musia na rekonštrukciu objednať. Má to ale jeden háčik. Keď projektant kreslil plány budovy, musel si odskočiť a jeho kolega mu tam medzitým dokreslil ešte niekoľko záchodových mís. Na niektorých záchodoch sú teraz iné, väčšie misy, inde sa zase kadejako prekrývajú, čo by možno bolo skvelé na výstave moderného umenia, no na Matfyze by sme radšej chceli funkčné záchody.

Keďže záchodov je na Matfyze veľa, nikomu sa to nechcelo ručne kontrolovať, a preto požiadali KSPákov o pomoc. Tí momentálne ale kvôli organizovaniu Letnej školy Trojstenu nič nestíhajú, a tak túto úlohu nechali na vás.

Úloha

Na vstupe dostanete pôdorys miestnosti pozostávajúci zo znakov . a O, ktoré označujú voľný priestor a časti záchodovej misy. Záchodová misa veľkosti \(k\) vyzerá ako rovnoramenný trojuholník, ktorého rohy sú označené znakom O. Medzi ľavým a pravým vrcholom je vždy \(2k-1\) prázdnych políčok (teda označených znakom .). Spodný vrchol trojuholníka sa nachádza o \(k\) políčok nižšie, presne v strede medzi ľavým a pravým vrcholom. Všetok ostatný priestor, vrátane vnútra misy, je označený znakom ..

Záchodové misy v nákrese môžu mať rôzne veľkosti, vždy ale pozostávajú práve z troch znakov O a nikdy nie sú otočené inak.

Vašou úlohou je skontrolovať, či sú všetky záchody správne zakreslené a neprekryvajú sa. V prípade, že je všetko v poriadku, je treba spočítať počet záchodov, ktoré sa na nákrese nachádzajú.

Formát vstupu

Na prvom riadku sa nachádzajú čísla \(s\) a \(r\), ktoré označujú počeť stĺpcov a riadkov nákresu. Na ďalších \(r\) riadkoch nasleduje nákres miestnosti, pričom každý riadok má práve \(s\) znakov.

Formát výstupu

Ak je nákres miestnosti v poriadku, na výstup vypíšte jediné čislo – počet záchodov, ktoré sa na nákrese nachádzajú. V opačnom prípade vypíšte Zly nakres.

Príklad

Input:

8 3
O.O..O.O
.O....O.
........

Output:

2

V tejto miestnosti sú iba 2 záchody rovnakej veľkosti vedľa seba.

Input:

11 5
O.....O....
......O...O
...........
...O.O.OO..
......O....

Output:

3

V ľavom hornom rohu je záchod veľkosti 3, napravo od neho záchod veľkosti 2 a v strede pod nimi je záchod veľkosti 1.

Input:

3 3
O.O
...
...

Output:

Zly nakres

Záchodu chýba tretí znak O – nákres je nesprávny.

  1. Akvárka sú prednáškové miestnosti na Matfyze.↩︎

  2. T2-ka je miestosť KSPákov na Matfyze. Pre bližšie predstavenie si tejto miestnosti – sú v nej skrine, gauče, stoly a veľká kopa eráru.↩︎

Na vyriešenie tejto úlohy nebolo treba vymýšlať žiadne komplikované postupy. Stačí nám iba postupne hľadať záchodové misy, kontrolovať či sa v ich vnútri nič nenachádza a spočítať ich.

To urobíme nasledovne: Budeme prechádzať načítaný nákres po riadkoch a hľadať dvojice znakov O medzi ktorými sú iba znaky . (bodka), a žiadne iné . V prípade, že k niektorému znaku O nenájdeme jeho dvojicu, záchod nie je správne zakreslený a teda aj celý nákres je nesprávny.

Každá nájdená dvojica znakov O je potenciálne záchodovou misou, ktorej veľkosť \(k\) vieme určiť zo vzdialenosti týchto znakov. Vďaka tomu vieme vypočítať, kde sa má nachádzať spodný vrchol trojuholníka reprezentujúceho misu. Následne si už len overíme, či sa na jeho mieste naozaj nachádza znak O.

Predtým, ako vyhlásime že je táto záchodová misa zakreslená správne, musíme ešte skontrolovať, či sa v jej vnútri naozaj nič nenachádza. Stačí nám jednoduchým cyklom skontrolovať plochu trojuholníka na nasledujúcich \(k\) riadkoch. Ak nájdeme iný znak ako ., záchod sa s niečím kryje a nákres je nesprávny.

Aby sme sa pri hľadaní ďalších mís nepomýlili, preznačíme si spodný vrchol na nejaký iný znak (napríklad #), ktorý budeme pri hľadaní ľavého horného vrcholu ignorovať. Nebudeme ho ale ignorovať pri kontrole vnútra trojuholníka, vďaka čomu zistíme prípadné prekrývanie s už skontrolovaným záchodom.

w, h = [int(x) for x in input().split()]
m = [list(input()) for _ in range(h)]

def check(r, c, s):
    global m
    if s <= 1:
        return False

    k = s // 2
    if m[r+k][c+k] != 'O':
        return False

    m[r][c] = '.'
    m[r][c+s] = '.'
    m[r+k][c+k] = '#'

    for y in range(r, r+k):
        for x in range(c+y, c+s-y):
            if m[y][x] != '.':
                return False

    return True

def abort():
    print('Zly nakres')
    exit()

start, cnt = None, 0
for r, row in enumerate(m):
    for c, char in enumerate(row):
        if start is None and char == 'O':
            start = c
        elif char == 'O':
            if check(r, start, c-start):
                cnt += 1
                start = None
            else:
                abort()
    
    if start is not None:
        abort()

print(cnt)
#include <iostream>
#include <vector>

using namespace std;

typedef vector<vector<char>> vv;

bool check(vv &v, int r, int c, int s) {
    if (s <= 1) return false;

    int k = s / 2;
    if (v[r+k][c+k] != 'O') return false;

    v[r][c] = '.';
    v[r][c+s] = '.';
    v[r+k][c+k] = '#';

    for (int y = r; y < r+k; y++) {
        for (int x = c+y; x < c+s-y; x++) {
            if (v[y][x] != '.') return false;
        }
    }

    return true;
}

int q() {
    cout << "Zly nakres\n";
    return 0;
}

int main() {
    ios_base::sync_with_stdio(false);  
    cin.tie(NULL); 

    int w, h;
    cin >> w >> h;
    vv v(h, vector<char>(w));

    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            cin >> v[i][j];
        }
    }

    int start = -1, cnt = 0;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            if (start == -1 && v[i][j] == 'O') {
                start = j;
            } else if (v[i][j] == 'O') {
                if (check(v, i, start, j-start)) {
                    cnt++;
                    start = -1;
                } else {
                    return q();
                }
            }
        }

        if (start != -1) {
            return q();
        }
    }

    cout << cnt << "\n";

    return 0;
}

Horné vrcholy trojuholníkov budeme hľadať v celom nákrese, čiže postupne prejdeme všetkých \(r \cdot s\) políčok. Pri kontrole vnútier trojuholníkov skontrolujeme určite menej ako \(r \cdot s\) políčok, keďže plocha pod záchodmi je určite menšia ako celý nákres, a pri prvom zistenom prekrývaní program končí. Výsledná časová zložitosť teda bude \(O(rs)\).

Pamäťová zložitosť bude rovnako \(O(rs)\) - pamätáme si celý nákres a zopár ďalších premenných.

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ť.