Prednáška 1718

Vyfarbovanie súvislých oblastí

• Uvažujme obrázok pozostávajúci z m krát n štvorčekov (pixelov).
• Farbu každého pixelu zapíšeme do jedného políčka dvojrozmerného poľa s m riadkami a n stĺpcami.
• V našom jednoduchom príklade budeme pracovať iba s piatimi farbami, ktoré budeme reprezentovať číslami 0,...,4 podľa nasledujúceho poľa (napríklad číslo 0 teda reprezentuje bielu farbu):

const char *farby[5] = {"white", "blue", "black", "yellow", "red"};

Napríklad obrázok

tak môže byť reprezentovaný nasledujúcim textovým súborom obsahujúcim najprv rozmery matice (čísla m a n) a za nimi samotné prvky matice:

11 17
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 0
 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0
 0 0 0 1 0 0 0 0 0 2 2 1 2 2 2 2 0
 0 0 0 1 0 0 0 0 0 2 0 1 0 0 0 2 0
 0 2 2 2 2 2 2 2 0 2 2 1 2 2 2 2 0
 0 2 0 1 0 0 0 2 0 0 0 1 0 0 0 0 0
 0 2 0 1 0 0 0 2 0 0 0 1 0 1 1 1 1
 0 2 0 1 1 1 1 2 1 1 1 1 0 1 0 0 1
 0 2 0 0 0 0 0 2 0 0 0 0 0 1 1 1 1
 0 2 2 2 2 2 2 2 0 0 0 0 0 0 0 0 0

Zameriame sa teraz na nasledujúci problém: používateľ zvolí (zadá na konzolu) súradnice niektorého štvorčeka a cieľom je ofarbiť nejakou farbou (napríklad červenou) celú súvislú oblasť rovnakej farby obsahujúcu daný štvorček. Napríklad pre obrazec vyššie a vstupné súradnice (2,1) (teda štvorček v treťom riadku a druhom stĺpci, keďže matica sa bude indexovať od nuly) by mal byť výstupom nasledujúci obrazec:

Podobný problém je napríklad často potrebné riešiť v rôznych nástrojoch na prácu s grafikou a podobne.

• Jednoduché útvary, napr. obdĺžnik, by sa dali vyfarbiť jednoduchými cyklami, naša súvislá oblasť ale môže mať veľmi zložitý tvar, s mnohými zákrutami, vetveniami, dierami a podobne.
• Pre každé políčko, ktoré prefarbíme, nesmieme zabudnúť skontrolovať všetkých jeho susedov a ak majú rovnakú farbu ako malo pôvodné políčko, tak prefarbiť aj ich, ich susedov, susedov ich susedov atď.
• Toto vieme ľahko zapísať rekurzívne: zafarbíme jedno políčko a potom rekurzívne zafarbujeme celú dosiahnuteľnú oblasť pre každého suseda rovnakej farby, akú malo pôvodne prefarbené políčko.
• Táto podúloha je menšia, lebo aspoň jedno políčko z nej ubudlo prvým prefarbením.

Vyfarbovanie pomocou rekurzívnej funkcie

Nasledujúca rekurzívna funkcia vyfarbi prefarbí políčko so súradnicami (riadok, stlpec) na cieľovú farbu farba a následne sa rekurzívne zavolá pre všetkých susedov tohto políčka, ktoré sú zafarbené pôvodnou farbou prefarbovanej oblasti.

/* Prefarbi súvislú jednofarebnú oblasť obsahujúcu 
 * pozíciu (riadok,stlpec) na farbu s číslom farba. */
void vyfarbi(int **a, int m, int n, 
             int riadok, int stlpec, int farba) {
    int staraFarba = a[riadok][stlpec];
    if (staraFarba == farba) {
        return;
    }
    a[riadok][stlpec] = farba;
    if (riadok - 1 >= 0 
        && a[riadok - 1][stlpec] == staraFarba) {
        vyfarbi(a, m, n, riadok - 1, stlpec, farba);
    }
    if (riadok + 1 < m 
        && a[riadok + 1][stlpec] == staraFarba) {
        vyfarbi(a, m, n, riadok + 1, stlpec, farba);
    }
    if (stlpec - 1 >= 0 
        && a[riadok][stlpec - 1] == staraFarba) {
        vyfarbi(a, m, n, riadok, stlpec - 1, farba);
    }
    if (stlpec + 1 < n 
        && a[riadok][stlpec + 1] == staraFarba) {
        vyfarbi(a, m, n, riadok, stlpec + 1, farba);
    }
}

Proces vyfarbovania môžeme animovať pomocou našej knižnice SVGdraw

• Výsledná animácia

V animácii okrem zmeny farby štvorčeka meníme aj farbu jeho rámčeka: pri zavolaní rekurzie sa zmení na hnedú a po skončení spracovania štvorčeka aj jeho susedov sa zmení na sivú. Hnedé sú teda vždy rámčeky štvorčekov uložené na zásobníku volaní.

Program s animáciou

• Program na vyfarbovanie súvislých oblastí obsahuje funkcie na inicializáciu matice, jej načítanie zo súboru, vykresľovanie jednotlivých štvorčekov a celej matice, ako aj uvoľnenie pamäte. Všetky tieto funkcie pracujú podobne ako pri príklade s výškovou mapou z prednášky 13.
• Funkcia main načíta maticu zo súboru vstup.txt a animáciu uloží do súboru matica.svg.
• Do rekurzívnej funkcie pridáme volania funkcie vykresliStvorcek, ktoré aktuálny štvorček v obrázku prekreslia novou farbou a menia aj farbu rámčeka. Za ňou vždy zavoláme funkciu drawing.wait, ktorá animáciu pozdrží, aby sme zmeny stihli na obrázku sledovať.

#include "SVGdraw.h"
#include <cstdio>
#include <cassert>

const char *farby[5] = {"white", "blue", "black", "yellow", "red"}; 

const int stvorcek = 40;    // velkost stvorceka v pixeloch
const int hrubkaCiary = 2;  // hrubka ciary v pixeloch
const double pauza = 0.3;   // pauza po kazdom kroku vyfarbovania v sekundach

/* Vytvori maticu s n riadkami a m stlpcami. */
int **vytvorMaticu(int m, int n) {
    int **a;
    a = new int *[m];
    for (int i = 0; i < m; i++) {
        a[i] = new int[n];
    }
    return a;
}

/* Uvolni pamat matice a s n riadkami a m stlpcami. */
void zmazMaticu(int **a, int m) {
    for (int i = 0; i < m; i++) {
        delete[] a[i];
    }
    delete[] a;
}

/* Vykresli stvorcek v riadku i a stlpci j 
   s farbou vyplne farba a farbou ciary farbaCiary. */
void vykresliStvorcek(int i, int j, 
                      const char * farba, 
                      const char * farbaCiary, 
                      SVGdraw &drawing) {
    drawing.setLineColor(farbaCiary);
    drawing.setLineWidth(hrubkaCiary);
    drawing.setFillColor(farba);
    drawing.drawRectangle(j * stvorcek, i * stvorcek, 
                          stvorcek, stvorcek);
}

/* Vykresli maticu a s n riadkami a m stlpcami. */
void vykresliMaticu(int **a, int m, int n, SVGdraw &drawing) {
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            vykresliStvorcek(i, j, farby[a[i][j]], "lightgray", drawing);
        }
    }
}

/* Nacita z textoveho suboru, na ktory ukazuje fr, 
   prvky matice a s n riadkami a m stlpcami. */
void nacitajMaticu(FILE *fr, int **a, int m, int n) {
    assert(fr != NULL);
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            fscanf(fr, "%d", &a[i][j]);
        }
    }
}

/* Prefarbi suvislu jednofarebnu oblast obsahujucu 
 * poziciu (riadok,stlpec) na farbu s cislom farba. */
void vyfarbi(int **a, int m, int n, 
             int riadok, int stlpec, int farba,
             SVGdraw &drawing) {
    int staraFarba = a[riadok][stlpec];
    if (staraFarba == farba) {
        return;
    }
    a[riadok][stlpec] = farba;
    vykresliStvorcek(riadok, stlpec, farby[farba], 
                     "brown", drawing);
    drawing.wait(pauza);
    if (riadok - 1 >= 0 && a[riadok - 1][stlpec] == staraFarba) {
        vyfarbi(a, m, n, riadok - 1, stlpec, farba, drawing);
    }
    if (riadok + 1 < m && a[riadok + 1][stlpec] == staraFarba) {
        vyfarbi(a, m, n, riadok + 1, stlpec, farba, drawing);
    }
    if (stlpec - 1 >= 0 && a[riadok][stlpec - 1] == staraFarba) {
        vyfarbi(a, m, n, riadok, stlpec - 1, farba, drawing);
    }
    if (stlpec + 1 < n && a[riadok][stlpec + 1] == staraFarba) {
        vyfarbi(a, m, n, riadok, stlpec + 1, farba, drawing);
    }
    vykresliStvorcek(riadok, stlpec, farby[farba], 
                     "lightgray", drawing);
    drawing.wait(pauza);
} 

int main() {
    FILE *fr = fopen("vstup.txt", "r");
    assert(fr != NULL);

    // nacitanie rozmerov matice
    int m, n;
    fscanf(fr, "%d %d", &m, &n);  
    // vytvorenie matice a nacitanie jej prvkov  
    int **a = vytvorMaticu(m, n);
    nacitajMaticu(fr, a, m, n);         
    fclose(fr);
        
    SVGdraw drawing(n * stvorcek, m * stvorcek, "matica.svg");
    vykresliMaticu(a, m, n, drawing);

    // nacitanie suradnic pociatocneho stvorceka 
    int riadok, stlpec;
    scanf("%d", &riadok);
    scanf("%d", &stlpec);

    vyfarbi(a, m, n, riadok, stlpec, 4, drawing);

    drawing.finish();
    zmazMaticu(a, m);
}

Abstraktný dátový typ

Abstraktný dátový typ (ADT) je abstrakcia dátovej štruktúry nezávislá od samotnej implementácie.

• Býva zadaný pomocou množiny operácií (hlavičiek funkcií), ktoré poskytuje
• Jeden abstraktný dátový typ môže byť implementovaný pomocou viacerých dátových štruktúr.

Témou prednášky 14 bol napríklad abstraktný dátový typ dynamická množina, ktorý poskytuje tri základné operácie:

• Zistenie či prvok patrí do množiny (contains).
• Pridanie prvku do množiny (add).
• Odobranie prvky z množiny (remove).

Videli sme implementácie pomocou neutriedeného poľa, utriedeného poľa, spájaného zoznamu, priameho adresovania a hašovania (pre jednoduchosť bez operácie remove).

Podobne za ADT môžeme považovať dynamické pole s operáciami add, length, get a set.

Výhodou abstraktných dátových typov je oddelenie implementácie dátovej štruktúry od programu, ktorý ju používa.

• Napríklad program pracujúci s dynamickou množinou prostredníctvom funkcií contains, add a remove možno rovnako dobre použiť pri implementácii množiny pomocou neutriedených polí, ako pri jeho implementácii pomocou hašovania.

Rad a zásobník

Dnes si ukážeme dva nové abstraktné dátové typy, zásobník a rad.

• Rad aj zásobník udržiavajú postupnosť nejakých prvkov.
• Typicky ide o úlohy alebo dáta čakajúce na spracovanie.
• Obidva poskytujú funkciu, ktorá vkladá nový prvok.
• Druhou základnou funkciou je výber jedného prvku, pričom rad sa od zásobníka líši tým, ktorý prvok sa vyberá.

Prvky radu a zásobníka môžu byť ľubovoľného typu. Namiesto konkrétneho typu (ako napríklad int alebo char) dnes budeme pracovať so všeobecným typom, ktorý nazveme dataType. Za ten možno dosadiť ľubovoľný konkrétny typ. Napríklad int dosadíme za dataType takto:

typedef int dataType;

• Pri využití tohto prístupu tak napríklad bude možné získať z radu prvkov typu int rad prvkov typu char zmenou v jedinom riadku programu.
• Taká istá úprava by sa dala spraviť aj pri ADT množina a dynamické pole.

Rad (queue)

Niekedy sa nazýva aj front(a).

• Z radu sa zakaždým vyberie ten jeho prvok, ktorý doň bol vložený ako prvý spomedzi jeho aktuálnych prvkov.
• Možno ho tak pripodobniť k radu pri pokladni v obchode.
• Takáto metóda manipulácie s dátami sa v angličtine označuje skratkou FIFO, podľa first in, first out.

Abstraktný dátový typ pre rad poskytuje tieto operácie (kde queue je názov štruktúry reprezentujúcej rad):

/* Inicializuje prázdny rad */
void init(queue &q);

/* Zistí, či je rad prázdny */
bool isEmpty(queue &q);

/* Pridá prvok item na koniec radu */
void enqueue(queue &q, dataType item);

/* Odoberie prvok zo začiatku radu a vráti jeho hodnotu */
dataType dequeue(queue &q);

/* Vráti prvok zo začiatku radu, ale nechá ho v rade */
dataType peek(queue &q);

/* Uvoľní pamäť */
void destroy(queue &q);

Zásobník (stack)

• Zo zásobníka sa naopak zakaždým vyberie ten prvok, ktorý doň bol vložený ako posledný.
• Môžeme si ho predstaviť ako stĺpec tanierov, kde umyté taniere dávame na vrch stĺpca a tiež z vrchu aj berieme taniere na použitie.
• Táto metóda manipulácie s dátami sa v angličtine označuje skratkou LIFO, podľa last in, first out.

Abstraktný dátový typ pre zásobník poskytuje tieto operácie (stack je názov štruktúry reprezentujúcej zásobník):

/* Inicializuje prázdny zásobník */
void init(stack &s);

/* Zistí, či je zásobník prázdny */
bool isEmpty(stack &s);

/* Pridá prvok item na vrch zásobníka */
void push(stack &s, dataType item);

/* Odoberie prvok z vrchu zásobníka a vráti jeho hodnotu */
dataType pop(stack &s);

/* Vráti prvok na vrchu zásobníka, ale nechá ho v zásobníku */
dataType peek(stack &s);

/* Uvoľní pamäť */
void destroy(stack &s);

Programy využívajúce rad a zásobník

Bez ohľadu na samotnú implementáciu vyššie uvedených funkcií vieme písať programy, ktoré ich využívajú. Napríklad nasledujúci program pracuje s radom:

#include <iostream>
using namespace std;

typedef int dataType;


/* Sem príde definícia štruktúry queue a potrebných funkcií. */


int main() {
    queue q;
    init(q);
    enqueue(q, 1);
    enqueue(q, 2);
    enqueue(q, 3);
    cout << dequeue(q) << endl;  // Vypíše 1
    cout << dequeue(q) << endl;  // Vypíše 2
    cout << dequeue(q) << endl;  // Vypíše 3
    destroy(q);
}

Podobne nasledujúci program pracuje so zásobníkom:

#include <iostream>
using namespace std;

typedef int dataType;

/* Sem príde definícia štruktúry stack a potrebných funkcií. */

int main() {
    stack s;
    init(s);
    push(s, 1);
    push(s, 2);
    push(s, 3);
    cout << pop(s) << endl;  // Vypíše 3
    cout << pop(s) << endl;  // Vypíše 2
    cout << pop(s) << endl;  // Vypíše 1
    destroy(s);
}

Poznámka:

• V objektovo-orientovanom programovaní (budúci semester) sa namiesto napr. push(s,10) píše niečo ako s.push(10)