Zadanie

Filip prišiel na dedinu za svojím starým ujom Záhradníkom. Poslala ho mama, pretože počula, že má ujo Záhradník problém na svojom poli. Totižto, na náhodných miestach sa na ňom objavujú diamanty. Uja Záhradníka však nezaujímajú nejaké diamanty. Z nich sa predsa nikto nenaje! On chce len vyorať svoje zamiaky, o ktoré sa celé leto staral. Problém je, že keď príde ujo Záhradník so svojím kombajnom na pole a začne orať, natrafí na diamant a kombajnu sa pokazí vidlica alebo dostane defekt. Preto poprosil Filipa, aby ich povyberal predtým, ako pôjde na pole. Filip si ale potrebuje dopozerať prednášku o logických obvodoch a spraviť si úlohu. Chce teda zisiť, či môže úlohu neodovzdať, školu nedokončiť a vyžiť z pozbieraných diamantov konca života. Kým Filip pozerá prednášku, počítanie diamantov zostalo na vás.

Úloha

Na vstupe dostanete pole ako mriežku \(n \times m\) znakov. V mriežke sú diamanty reprezentované zoskupením \(2 \times 2\) znakov nasledovne:

/\
\/

Vašou úlohou je ich spočítať. Na poli môžu byť porozhadzované aj všeliaké iné paličky, korienky a kamienky, takže si dajte pozor, aby ste započítali len diamanty.

Formát vstupu

V prvom riadku vstupu je číslo \(n\) udávajúce počet riadkov, ktoré budú reprezentovať naše pole. Nasleduje \(n\) riadkov, na každom z nich bude reťazec dĺžky \(m\), ktorý reprezentuje jeden riadok mriežky.

Sú 4 sady vstupov, v ktorých platia tieto obmedzenia:

Sada 1 2 3 4
\(1 \leq n, m \leq\) \(100\) \(100\) \(1\,000\) \(5\,000\)

Formát výstupu

Vypíš jeden riadok a v ňom jedno celé číslo, udávajúce počet diamantov v poli.

Príklady

Input:

10 10
......./\.
.......\/.
./\.......
./\.......
.\/.......
.\/.......
....../\..
/\....\/\.
\/....\//.
..........

Output:

4

Input:

10 10
/\/\......
\/\/./\...
..../\/...
....\/....
.../\.....
...\/./\\.
......\//.
......\/..
..../\\/\.
....\//\/.

Output:

8

Čo bolo našou úlohou

Našou úlohou bolo prejsť \(n\) riadkov stringu (reťazca) a spočítať diamanty v nich.

Ako sme to urobili

Priamočiare a najoptimálnejšie riešene je, že kontrolujme, či \(i\)-tý znak aktuálneho riadku je /, \(i+1\) - tý znak je \ a či v nasledujúcom riadku \(i\)-tý znak je \ a \(i+1\) - tý znak je /. Treba si dať pozor, že v tomto prípade neprechádzame posledný riadok, pretože pod ním nie je už žiaden potenciálny diamant a prehladávanie by nám len hodilo chybu, to isté platí aj pre posledný znak v riadku.

Časová zložitosť

Časová zložitosť je \(O(nm)\), pretože prejdeme \(n\) riadkov dva krát (iba posledný riadok prejdeme raz) a v každom riadku prejdeme znak 2 krát (okrem posledného znaku v každom riadku). Keďže v každom riadku je \(m\) znakov a násobenie alebo pripočítavanie konštánt v časovej zložitosti zanedbávame, dostaneme \(O(nm)\).

Pamäťová zložitosť

Tu si treba dať pozor, že optimálna pamäťová zložitosť je \(O(m)\), pretože nám stačí pamätať si 2 riadky po \(m\) znakov, keďže postupne načítavame riadky a nahradzujeme ich novými.

Príklad

Pozrime sa, ako by sme si poradili s prvým príkladom zo zadania.

10 10
......./\.
.......\/.
./\.......
./\.......
.\/.......
.\/.......
....../\..
/\....\/\.
\/....\//.
..........

Načítame si zo vstupu prvý a druhý riadok a kontrolujeme znaky: Znak na prvom mieste (index 0) v prvom riadku je na druhom mieste tiež a to isté aj v druhom riadku, takže tu diamant nie je. Prvý diamant čo nájdeme, je stále v prvom a druhom riadku. Na 8. mieste v prvom riadku je / a 9. mieste je \. Keďže toto nám sedí, pozrieme sa na druhý riadok a tam tiež sedí, pretože na 8. mieste v prvom riadku je \ a 9. mieste je /. Máme teda prvý diamant a postupujeme ďalej tak, že načítame tretí riadok a prvý zahodíme.

R, C = map(int, input().split())

res = 0
line1 = "." * C
for _ in range(R):
    line2 = input()
    for x in range(C - 1):
        if line1[x:x+2] == "/\\" and line2[x:x+2] == "\\/":
            res += 1
    line1 = line2

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

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<string> map(n);

    getline(cin, map[0]);  // reads the rest of the line
    for (int r = 0; r < n; r++) {
        getline(cin, map[r]);
    }

    int count = 0;
    for (int r = 0; r < n-1; r++) {
        for (int c = 0; c < m-1; c++) {
            if (map[r][c] == '/' && map[r][c+1] == '\\' && map[r+1][c] == '\\' && map[r+1][c+1] == '/') {
                count++;
            }
        }
    }
    
    cout << count << "\n";
    return 0;
}

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