Č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;
}