Zadanie
Bol daždivý októbrový deň. Vonku MASÍVNE pršalo. Vladko nemal čo robiť. Len tak sa pozeral von oknom. Po chvíli si všimol, že sa na chodníku vytvorilo viacero oblastí, z kade voda steká na rovnaké miesto. Vladka veľmi zaujíma, ktoré miesta na chodníku patria do akej oblasti. Pomôžete mu to zistiť? Vladko je však veľmi vyberavý. Páči sa mu iba také označenie oblastí, pre ktoré platí: ak máme dve oblasti - \(O_1, O_2\) oblasť na ktorú pri prechode zľava doprava, zhora dole narazíme ako prvú, musí byť označená menším číslom.
Úloha
Chodník je reprezentovaný dvojrozmerným poľom. Voda steká z políčka \(CH[i][j]\) na najnižšieho nižšieho suseda. Ak má viacero susedov rovnakú výšku, priorita stekania ide: S, Z, J, V. Vašou úlohou je zistiť, ktoré políčka patria do rovnakej oblasti. Oblasti číslujeme od 1. Očíslovanie oblastí musí spĺňať Vladkovu podmienku.
Formát vstupu
V prvom riadku vstupu dostanete 2 čísla - \(n, m\) - rozmery chodníka. Ďalej nasleduje \(n\) riadkov po \(m\) čísiel.
V jednotlivých sadách platia nasledujúce obmedzenia:
Sada | 1 | 2 | 3 | 4 |
---|---|---|---|---|
\(1 \leq n, m \leq\) | \(10\) | \(100\) | \(500\) | \(500\) |
\(1 \leq \max CH[i][j] \leq\) | \(100\) | \(4\cdot10^4\) | \(2,5\cdot 10^5\) | \(10^9\) |
Formát výstupu
Vypíšte \(n\) riadkov po \(m\) stĺpcoch. Hodnota \(CH[i][j]\) značí, do ktorej oblasti patrí políčko \(CH[i][j]\).
Príklady
Input:
3 3
1 1 1
1 2 1
1 1 1
Output:
1 2 3
4 2 5
6 7 8
Voda steká z políčka \(CH[1][1]\) na políčko \(CH[0][1]\), pretože spomedzi ostatných susedov \(CH[1][1]\) má najvyššiu prioritu
Input:
2 2
1 1
1 1
Output:
1 2
3 4
Voda nemá kam stekať zo žiadneho políčka. Odpoveď:
2 1
3 4
by nevyhohovala Vladkovým podmienkam, pretože oblasť 2 by sme stretli pred oblasťou 1.
Bruteforce
Bruteforce môžeme spraviť tak, že si odsimulujeme tok vody z každého políčka. Pre každé políčko si zapamätáme, aké je jeho koncové políčko. Všetky políčka, čo stekajú na rovnaké miesto budú v rovnakej oblasti.
Keď toto spravíme pre všetky políčka, tak už nám iba stačí prideliť čísla oblastiam. Čísla oblastiam priraďujeme tak, že pri prechode poľom (zľava doprava, zhora dole) si pamätáme, na ktorú oblasť sme narazili ako prvú. Rôzne oblasti odlišujeme podľa toho, že políčka v nich stekajú na rôzne koncové miesta.
Priradiť koncové políčko jednému políčku vieme v čase \(O(nm)\). Totiž, prinajhoršom budeme musieť prejsť pre toto políčko celé pole. To znamená, že časová zložitosť tohto riešenia je \(O(n^2m^2)\).
Pre každé políčko si potrebujeme pamätať, aké je jeho koncové políčko. Taktiež si potrebujeme pre každé koncové políčko pamätať, aké je číslo oblasti, ktorá mu prináleží. Vieme však, že koncových políčok môže byť najviac \(nm\) To znamená, že toto riešenie má pamäťovú zložitosť \(O(nm)\).
Zaujímavá myšlienka
Povedzme, že pri hľadaní koncového políčka pre políčko \(CH[i][j]\) sme prešli políčkom \(CH[k][l]\), pre ktoré už vieme, kam z neho steká voda. Koncové políčko pre \(CH[i][j]\) musí teda byť rovnaké ako koncové políčko pre \(CH[k][l]\). To kvôli tomu, že stekanie vody je jednoznačné - všetci susedia, ktorí stekajú na políčko \(CH[k][l]\) budú z neho ďalej stekať na rovnaké miesto, ako steká ono samo.
Lepšie riešenie
Bruteforce by sme mohli vylepšiť tak, že by sme políčkami prechádzali od najnižšieho k najvyššiemu. Keď by sme sa potom dostali k nejakému políčku \(CH[i][j]\), tak by mohli nastať 2 prípady: 1) Všetci jeho susedia sú vyšší. V tomto prípade z neho voda nemá kam stekať. To znamená, že jeho koncovým políčkom bude ono samo. 2) Nejaký jeho sused je od neho nižší. Keďže políčka riešime od najnižšieho, tak už máme vyriešených všetkých jeho nižších susedov. Teda tomuto políčku priradíme koncové políčko suseda, na ktoré steká ono samo.
Každé políčko vieme riešiť v konštantom čase (pozrieme sa na jeho 4 susedov). Keďže políčka riešime od najnižšieho k najvyššiemu, tak si potrebujeme políčka utriediť podľa výšky. Na konci potrebujeme ešte raz prejsť poľom, aby sme priradili číslo oblasti. To znamená, že časová zložitosť tohto riešenia je \(O(nm\log(nm))\).
Potrebujeme si pamätať políčka zo vstupu a potrebujeme ďalšie pole, v ktorom si ich budeme pamätať utriedené podľa výšky. To znamená, že toto riešenie bude mať pamäťovú zložitosť \(O(nm)\).
Optimálne riešenie
Náš bruteforce sa dá vylepšiť aj inak ako tak, že budeme prechádzať
políčkami od najnižšieho po najvyššie. Povedzme, že potrebujeme zistiť,
kam steká políčko \(CH[i][j]\). Budeme
to simulovať. Pri našej simulácii si však budeme v poli pamätať, ktoré
všetky políčka sme navštívili, keď voda stekala z políčka \(CH[i][j]\). Toto druhé pole si nazvime
tok
. Povedzme, že sme počas simulácie toku z políčka \(CH[i][j]\) natrafili na políčko \(CH[k][l]\), ktoré už máme vyriešené, alebo
z neho nemá kam stekať voda. To znamená, že všetky políčka v simulovanom
toku budú mať rovnaké koncové políčko ako \(CH[k][l]\).
Prejsť celým poľom vieme v čase \(O(nm)\). Ak by sme natrafili na políčko, ktoré máme už vyriešené (lebo bolo v toku iného políčka), tak ho môžeme preskočiť a ísť spracovávať ďalšie. To znamená, že toto riešenie má časovú zložitosť \(O(nm)\).
Pre každé políčko si potrebujeme pamätať, aké je jeho koncové
políčko. Taktiež si potrebujeme pamätať tok
, ale ten môže
mať dĺžku najviac \(nm\). To znamená,
že toto riešenie má pamäťovú zložitosť \(O(nm)\).
= [int(x) for x in input().split()]
n, m = [[0, 1], [1, 0], [0, -1], [-1, 0]]
p = 1000000001
inf = [[inf for i in range(m + 2)] for j in range(n + 2)]
heights
for i in range(1, n + 1):
= [int(x) for x in input().split()]
riadok for j in range(1, m + 1):
= riadok[j - 1]
heights[i][j]
= [[-1 for i in range(m + 1)] for j in range(n + 1)]
odtoky
for i in range(1, n + 1):
for j in range(1, m + 1):
min = heights[i][j]
= -1
smer for k in range(4):
if heights[i + p[k][0]][j + p[k][1]] <= min:
= k
smer min = heights[i + p[k][0]][j + p[k][1]]
if min == heights[i][j]:
= -1
smer = smer
odtoky[i][j]
= [[0 for i in range(m + 1)] for j in range(n + 1)]
ans = 1
kod_oblasti
for i in range(1, n + 1):
for j in range(1, m + 1):
= i
x_now = j
y_now = []
tok while odtoky[x_now][y_now] != -1 and ans[x_now][y_now] == 0:
tok.append([x_now, y_now])= x_now + p[odtoky[x_now][y_now]][0]
x_next = y_now + p[odtoky[x_now][y_now]][1]
y_next = x_next
x_now = y_next
y_now
tok.append([x_now, y_now])if not ans[x_now][y_now]:
= kod_oblasti
ans[x_now][y_now] += 1
kod_oblasti = ans[x_now][y_now]
fill for k in range(len(tok)):
0]][tok[k][1]] = fill
ans[tok[k][
for i in range(1, n + 1):
for j in range(1, m):
print(ans[i][j], end=" ")
print(ans[i][m])
#include <iostream>
#include <cstdlib>
#include <vector>
using namespace std;
typedef long long ll;
const ll inf = 1000000001;
int main(){
//ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n, m; // n, m <= 5*10^2
>> n >> m;
cin // 0 <= hodnoty na vstupe <= 10^9;
[n+2][m+2];
ll heightsint p[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; //zmenil som si poradie priorit: S, Z, J, V
for (int i = 0; i < n+2; i++){
[i][0] = inf;
heights[i][m+1] = inf;
heights}
for (int i = 0; i < m+2; i++){
[0][i] = inf;
heights[n+1][i] = inf;
heights}
for (int i = 1; i <= n; i++){
for (int j = 1; j <= m; j++){
>> heights[i][j];
cin }
}
int odtoky[n+1][m+1];
for (int i = 1; i <= n; i++){
for (int j = 1; j <= m; j++){
= heights[i][j];
ll min int smer = -1;
for (int k = 0; k < 4; k++){
if (heights[i+p[k][0]][j+p[k][1]] <= min){
= k;
smer = heights[i+p[k][0]][j+p[k][1]];
min }
}
if (min == heights[i][j]){
= -1;
smer }
[i][j] = smer;
odtoky}
}
[n+1][m+1];
ll ansfor (int i = 0; i < n+1; i++){
for (int j = 0; j < m+1; j++){
[i][j] = 0;
ans}
}
= 1;
ll kod_oblasti for (int i = 1; i <= n; i++){
for (int j = 1; j <= m; j++){
int x_now = i;
int y_now = j;
<vector<int>> tok;
vectorwhile (odtoky[x_now][y_now] != -1 && (ans[x_now][y_now] == 0)){
.push_back({x_now, y_now});
tokint x_next = x_now + p[odtoky[x_now][y_now]][0];
int y_next = y_now + p[odtoky[x_now][y_now]][1];
= x_next;
x_now = y_next;
y_now }
.push_back({x_now, y_now});
tokif (!ans[x_now][y_now]){
[x_now][y_now] = kod_oblasti;
ans++;
kod_oblasti}
= ans[x_now][y_now];
ll fill for (ll k = 0; k < tok.size(); k++){
[tok[k][0]][tok[k][1]] = fill;
ans}
}
}
for (int i = 1; i <= n; i++){
for (int j = 1; j < m; j++){
<< ans[i][j] << " ";
cout }
<< ans[i][m] << "\n";
cout }
//vrati to tu mapu ako jeden string
}
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ť.