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.
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.
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:
Vypíš jeden riadok a v ňom jedno celé číslo - počet dolín, do ktroých sa vie dostať Paulínka.
4 3 2 1
2 1 2
1 4 3
2 3 5
1 4 3
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.
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
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)
4 3 3 0
2 1 2
1 4 3
2 3 5
1 4 3
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)
Š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.
Š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 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;
}
Korešpondenčný seminár z programovania zastrešuje občianske združenie Trojsten.
Trojsten, o.z.
FMFI UK, Mlynská dolina
842 48 Bratislava
Programátorská súťaž pre základoškolákov
Materiály a úlohy na výučbu programovania
Intenzívny programátorský zážitok v lete