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)\).

n, m = [int(x) for x in input().split()]
p = [[0, 1], [1, 0], [0, -1], [-1, 0]]
inf = 1000000001
heights = [[inf for i in range(m + 2)] for j in range(n + 2)]

for i in range(1, n + 1):
    riadok = [int(x) for x in input().split()]
    for j in range(1, m + 1):
        heights[i][j] = riadok[j - 1]

odtoky = [[-1 for i in range(m + 1)] for j in range(n + 1)]

for i in range(1, n + 1):
    for j in range(1, m + 1):
        min = heights[i][j]
        smer = -1
        for k in range(4):
            if heights[i + p[k][0]][j + p[k][1]] <= min:
                smer = k
                min = heights[i + p[k][0]][j + p[k][1]]
        if min == heights[i][j]:
            smer = -1
        odtoky[i][j] = smer

ans = [[0 for i in range(m + 1)] for j in range(n + 1)]
kod_oblasti = 1

for i in range(1, n + 1):
    for j in range(1, m + 1):
        x_now = i
        y_now = j
        tok = []
        while odtoky[x_now][y_now] != -1 and ans[x_now][y_now] == 0:
            tok.append([x_now, y_now])
            x_next = x_now + p[odtoky[x_now][y_now]][0]
            y_next = y_now + p[odtoky[x_now][y_now]][1]
            x_now = x_next
            y_now = y_next
        tok.append([x_now, y_now])
        if not ans[x_now][y_now]:
            ans[x_now][y_now] = kod_oblasti
            kod_oblasti += 1
        fill = ans[x_now][y_now]
        for k in range(len(tok)):
            ans[tok[k][0]][tok[k][1]] = fill

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
    cin >> n >> m;
    // 0 <= hodnoty na vstupe <= 10^9;
    ll heights[n+2][m+2];
    int 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++){
        heights[i][0] = inf;
        heights[i][m+1] = inf;
    }
    for (int i = 0; i < m+2; i++){
        heights[0][i] = inf;
        heights[n+1][i] = inf;
    }
    
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            cin >> heights[i][j];
        }
    }
    
    int odtoky[n+1][m+1];
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            ll min = heights[i][j];
            int smer = -1;
            for (int k = 0; k < 4; k++){
                if (heights[i+p[k][0]][j+p[k][1]] <= min){
                    smer = k;
                    min = heights[i+p[k][0]][j+p[k][1]];
                }
            }
            if (min == heights[i][j]){
                smer = -1;
            }
            odtoky[i][j] = smer;
        }
    }
    
    ll ans[n+1][m+1]; 
    for (int i = 0; i < n+1; i++){
        for (int j = 0; j < m+1; j++){
            ans[i][j] = 0;
        }
    }
    ll kod_oblasti = 1;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            int x_now = i;
            int y_now = j;
            vector<vector<int>> tok;
            while (odtoky[x_now][y_now] != -1 && (ans[x_now][y_now] == 0)){
                tok.push_back({x_now, y_now});
                int x_next = x_now + p[odtoky[x_now][y_now]][0];
                int y_next = y_now + p[odtoky[x_now][y_now]][1];
                x_now = x_next;
                y_now = y_next;
            }
            tok.push_back({x_now, y_now});
            if (!ans[x_now][y_now]){
                ans[x_now][y_now] = kod_oblasti;
                kod_oblasti++;
            }
            ll fill = ans[x_now][y_now];
            for (ll k = 0; k < tok.size(); k++){
                ans[tok[k][0]][tok[k][1]] = fill;
            }
        }
    }
    for (int i = 1; i <= n; i++){
        for (int j = 1; j < m; j++){
            cout << ans[i][j] << " ";
        }
        cout << ans[i][m] << "\n";
    }
    //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ť.