Zoznam úloh

3. Predajne všade

Zadanie

Keďže žijeme v konzummnej spoločnosti, je všade strašne veľa obchodov. Paulínka už toho mala plné zuby a v záujme zmeny scenérie sa vydala do hôr.

Aj v horách už však v dnešnej dobe číhajú nástrahy kapitalizmu. Paulínka sa urputne snažila im vyhnúť a stratila sa pri tom. Jediné čo vie, je že potrebuje ísť z hôr dole. Väčšinou však existuje viac spôsobov ako ísť z hôr dole, a Paulínka by chcela vedieť koľko ich je.

Úloha

Na vstupe dostanete mapu hôr s vrstevnicami (2d pole s nadmorskými výškami jednotlivých bodov, po ktorých môže Paulínka prechádzať) a miesto, kde sa Paulínka momentálne (na začiatku) nachádza. Paulínka sa v tomto poli môže pohybovať iba po políčkach susediacich hranou a vždy iba smerom dole (na nižšiu nadmorskú výšku), teda na políčko, ktorého nadmorská výška je ostro menšia ako nadmorská výška políčka, na ktorom je.

Vašou úlohou je spočítať, koľko existuje dolín (políčka, z ktorých sa už nedá ísť nižšie) do ktorých sa Paulínka vie dostať a vypísať to číslom na jediný riadok výstupu.

Formát vstupu

V prvom riadku vstupu sú čísla $r$, $s$, $y$ a $x$ ($1 \leq r, s \leq 10^6$, $0 \leq y < r$, $0 \leq x < s$), udávajúce počet riadkov a stĺpcov mapy, a súradnice bodu, v ktorom Paulínka začína.

V ďalších $r$ riadkoch je po $s$ čísel $h_{y,x}$ ($1 \leq h_{y,x} \leq 10^9$), udávajúce nadmorské výšky jednotlivých bodov na mape.

V jednotlivých sadách platia nasledujúce obmedzenia:

Sada 1 2 3 4
$r, s \leq$ $10^6$ $10^6$ $10^3$ $10^6$

Zároveň platia pre konkrétne sady nasledujúce vlastnosti:

  • V sade 1 je mapa pásik, teda počet riadkov je 1
  • V sade 2 platí, že Paulínka sa vie dostať na akékoľvek miesto na mape

Formát výstupu

Vypíš jeden riadok a v ňom jedno celé číslo - počet dolín, do ktroých sa vie dostať Paulínka.

Príklady

Vstup

4 3 2 1
2 1 2
1 4 3
2 3 5
1 4 3

Výstup

2

Začína na bode (1, 2), odtiaľ môže ísť iba na (0, 2). Z (0, 2) môže ísť iba na (0, 1) a (0, 3). Odtiaľ už nemôže ísť nikam, takže tie dva body sú doliny.

Vstup

5 5 2 2
2 1 2 1 2
1 4 3 4 1
2 3 5 3 2
1 4 3 4 1
2 1 2 1 2

Výstup

8

Začína na bode (2, 2), odtiaľ sa môže dostať do všetkých dolín na mape, a tých je 8. (všetky body s nadmorskou výškou 1)

Vstup

4 3 3 0
2 1 2
1 4 3
2 3 5
1 4 3

Výstup

1

Začína na bode (0, 3), ktorý je sám dolinou. Žiadne ďalšie doliny nenájde.

Cieľom bolo nájsť (resp. spočítať) všetky lokálne minimá (políčka, ktorých čísla sú ostro menšie ako čisla všetkých ich susedov) v mriežke (2d pole)

1. Subtask

Špeciálna vlastnosť prvej sady robí z 2d úlohy 1d úlohu. Stačí nám teda pozrieť sa od začiatočného políčka mriežky naľavo a napravo, a posúvať sa dokým sú čísla v ďalších políčkach menšie.

Prechádzame cez všetky políčka, takže časová zložitosť je $O(r * s)$. Všetky si ich musíme aj pamätať, takže aj pamäťová zložitosť je $O(r * s)$

Toto riešenie však prejde iba na prvej sade.

2. Subtask

Špeciálna vlastnosť druhej sady nám dovoľuje problém zredukovať na hladanie lokálnych miním.

Prechádzame cez všetky políčka, takže časová zložitosť je $O(r * s)$. Všetky si ich musíme aj pamätať, takže aj pamäťová zložitosť je $O(r * s)$

Toto riešenie však prejde iba na druhej sade.

Úplné riešenie

Úplné riešenie tejto úlohy spočíva v tom, že si mriežku interpretujeme ako graf, kde každé políčko je vrchol a každá strana medzi políčkami je hrana. Na takomto grafe následne spustíme implementáciu ľubovolného prehľadávacieho algoritmu (napr. BFS alebo DFS), s tým že budeme navštevovať iba vrcholy, ktorých výška je menšia ako výška vrchola, z ktorého donich ideme. Vrchol z ktorého na základe takejto podmienky nemôžme nikam ísť je lokálne minimum.

Časová zložitosť prehľadávacích algorimov je vo všeobecnosti $O(n + m)$, kde $n$ je počet vrcholov grafu a $m$ je počet hrán. Tým že náš graf vznikol z mriežky, počet hrán je lineárne závislý od počtu vrcholov. Počet vrcholov je počet políčok v mriežke, teda $r * s$. Časová zložitosť tohto riešenia je teda $O(r * s)$.

Pamäťová zložitosť je tiež $O(r * s)$, lebo si všetky políčka v mriežke musíme pamätať.

# Načítame vstup
r, s, y, x = [int(i) for i in input().split(" ")]
grid = [[int(i) for i in input().split(" ")] for _ in range(r)]

# Ideme robiť BFS, takže si pripravíme queue
# Zárovaň si budeme v ďalšom 2d poli pamätať, ktoré políčka sme už navštívili
# a počítať, koľko z nich boli lokálne minimá / doliny
queue = [(y, x)]
visited = [[False for _ in range(s)] for _ in range(r)]
visited[y][x] = True
count = 0

while len(queue) > 0:
    # Vytiahneme prvé políčko z queue a zistíme si jeho výšku
    cur_y, cur_x = queue.pop(0)
    height = grid[cur_y][cur_x]
    is_min = True

    # Skontrolujeme postupne políčka nahor, napravo, nadol
    # a naľavo od aktuálneho
    for y_diff, x_diff in [(-1, 0), (0, 1), (1, 0), (0, -1)]:
        next_y, next_x = cur_y + y_diff, cur_x + x_diff
        # Skotrolujeme či políčko existuje, inak ho preskočíme
        if next_y < 0 or next_y >= r:
            continue
        if next_x < 0 or next_x >= s:
            continue
        # Skotrolujeme či je políčko nižšie ako aktuálne,
        # teda či naňho vieme ísť, ak nie, tak ho preskočíme
        if grid[next_y][next_x] >= height:
            continue
        # Skontrolujeme čí sme tam boli, a ak nie, tak tam ideme
        if not visited[next_y][next_x]:
            queue.append((next_y, next_x))
            visited[next_y][next_x] = True
        # Bez ohľadu na to, či tam ideme, prítomnosť nižšieho suseda
        # znamená, že aktuálne políčko nemôže byť lokálnym minimom
        is_min = False

    # Ak všetky existujúce susedné políčka väčšie alebo rovné,
    # je aktuálne políčko lokálnym minimom, a keďže sme sa doňho
    # očividne dostali, chceme ho započítať
    if is_min:
        count += 1
print(count)
#include <iostream>
#include <queue>
#include <utility>
#include <vector>

using namespace std;

typedef queue<pair<int, int>> qc;
typedef vector<pair<int, int>> vc;

int main() {
    // Načítame vstup
    // Zárovaň si budeme v ďalšom 2d poli pamätať, ktoré políčka sme už navštívili
    int r, s, y, x;
    cin >> r >> s >> y >> x;
    int grid[r][s];
    bool visited[r][s];
    for (int y = 0; y < r; y++) {
        for (int x = 0; x < s; x++) {
            cin >> grid[y][x];
            visited[y][x] = false;
        }
    }
    visited[y][x] = true;

    // Ideme robiť BFS, takže si pripravíme queue
    qc queue;
    queue.emplace(y, x);
    // Zároveň chceme počítať, koľko z nich boli lokálne minimá / doliny
    int count = 0;

    while (!queue.empty()) {
        // Vytiahneme prvé políčko z queue a zistíme si jeho výšku
        pair<int, int> cur = queue.front();
        queue.pop();
        int height = grid[cur.first][cur.second];
        bool is_min = true;

        // Skontrolujeme postupne políčka nahor, napravo, nadol
        // a naľavo od aktuálneho
        for (pair<int, int> diff : vc({{-1, 0}, {0, 1}, {1, 0}, {0, -1}})) {
            pair<int, int> next = {cur.first + diff.first, cur.second + diff.second};
            // Skotrolujeme či políčko existuje, inak ho preskočíme
            if (next.first < 0 || next.first >= r) continue;
            if (next.second < 0 || next.second >= s) continue;
            // Skotrolujeme či je políčko nižšie ako aktuálne,
            // teda či naňho vieme ísť, ak nie, tak ho preskočíme
            if (grid[next.first][next.second] >= height) continue;
            // Skontrolujeme čí sme tam boli, a ak nie, tak tam ideme
            if (!visited[next.first][next.second]) {
                queue.push(next);
                visited[next.first][next.second] = true;
            }
            // Bez ohľadu na to, či tam ideme, prítomnosť nižšieho suseda
            // znamená, že aktuálne políčko nemôže byť lokálnym minimom
            is_min = false;
        }

        // Ak všetky existujúce susedné políčka väčšie alebo rovné,
        // je aktuálne políčko lokálnym minimom, a keďže sme sa doňho
        // očividne dostali, chceme ho započítať
        if (is_min) count++;
    }
    cout << count << "\n";
    return 0;
}
Pre odovzdávanie sa musíš prihlásiť.
Trojsten

Korešpondenčný seminár z programovania zastrešuje občianske združenie Trojsten.

Kontakt
Ďalšie projekty