Prednáška 18

Opakovanie: zásobník a rad

• Zásobník (angl. stack) a rad alebo front (angl. queue) sú abstraktné dátové typy, ktoré udržiavajú postupnosť nejakých prvkov.
• Obidva typy podporujú vloženie prvku a výber prvky
• Zo zásobníka sa vyberá prvok, ktorý v ňom pobudol najkratšie, z radu prvok, ktorý v ňom bol najdlhšie
• Zásobník tak pripomína stĺpec čistých tanierov v reštaurácii, rad pripomína rad pri pokladni

Konkrétne funkcie hlavičky funkcií

void init(stack &s);
bool isEmpty(stack &s);
void push(stack &s, dataType item); // vlozenie prvku
dataType pop(stack &s);    // vyber prvku
dataType peek(stack &s);
void destroy(stack &s);

void init(queue &q);
bool isEmpty(queue &q);
void enqueue(queue &q, dataType item); // vlozenie prvku
dataType dequeue(queue &q);  // vyber prvku
dataType peek(queue &q);
void destroy(queue &q);

• Pre obidva typy sme videli implementáciu v poli aj v spájanom zozname
• Hlavné funkcie vkladania a vyberania sú v obidvoch implementáciách rýchle a jednoduché

Videli sme tiež, že obidve štruktúry sa dajú použiť na ukladanie dát alebo úloh, ktoré ešte treba vyriešiť

• Dnes uvidíme ďalšie príklady

Použitie zásobníka a radu: nerekurzívny Quick Sort

Pripomeňme si triedenie Quick Sort z 11. prednášky:

void swap (int &x, int &y) {
    int tmp = x;
    x = y;
    y = tmp;
}

int partition(int a[], int left, int right) {
    int pivot = a[left];     
    int lastSmaller = left;
    
    for (int unknown = left + 1; unknown <= right; unknown++) {
        if (a[unknown] < pivot) {
            lastSmaller++;
            swap(a[unknown], a[lastSmaller]);
        }
    }   
    swap(a[left],a[lastSmaller]); 
    return lastSmaller;
}

void quicksort(int a[], int left, int right) {
    if (left >= right) {
        return; 
    }
    
    int middle = partition(a, left, right);
        
    quicksort(a, left, middle-1);  
    quicksort(a, middle+1, right);   
}

int main() {
  // ...
  quicksort(a, 0, N-1);
  // ...
}

Namiesto rekurzie môžeme použiť aj zásobník úsekov, ktoré ešte treba dotriediť.

struct usek {
    int left;
    int right;
};

typedef usek dataType;

/* Sem pride definicia struktury stack a vsetkych potrebnych funkcii. */

/* Sem pridu funkcie swap a partition rovnake ako vyssie. */

void quicksort(int a[], int n) {
    stack s;
    init(s);
    
    usek u;
    u.left = 0;
    u.right = n-1;
    push(s,u);
    
    while (!isEmpty(s)) {
        u = pop(s);
        // vynechame useky dlzky 0 a 1
        if (u.left >= u.right) {
            continue;
        }
        
        int middle = partition(a, left, right);
        
        usek u1;
        u1.left = u.left;
        u1.right = middle - 1;
        usek u2;
        u2.left = middle + 1;
        u2.right = u.right;
        push(s,u2);
        push(s,u1);
    }
    
    destroy(s);
}

int main() {
  // ...
  quicksort(a, N);
  // ...
}

• Tento program triedi úseky v rovnakom poradí, ako rekurzívny Quick Sort, lebo po rozdelení poľa na dve časti dá na vrch zásobníka úsek zodpovedajúci jeho ľavej časti. Až keď sa táto ľavá časť a všetky podúlohy, ktoré z nej vzniknú, spracuje, dôjde na spracovanie pravej časti poľa.
• Pri triedení Quick Sort však na tomto poradí nezáleží, takže by sme mohli jednotlivé úseky vkladať na zásobník aj v opačnom poradí.
• Alebo by sme namiesto zásobníka mohli použiť rad. Potom by najskôr rozdelil ľavú aj pravú časť na ďalšie podčasti a potom by delil každú z týchto podčastí atď.

Na zamyslenie: ako by mohla vyzerať nerekurzívna verzia triedenia Merge Sort? Prečo sa nedá použiť rovnaký prístup ako pri triedení Quick Sort?

Vyfarbovanie súvislých oblastí

Uvažujme obrazec daný obdĺžnikovou maticou o m riadkoch a n stĺpcoch. Obdĺžnikové plátno je v takom prípade rozdelené na m krát n „štvorčekov” určitej konštantnej veľkosti, pričom jednotlivé prvky matice zodpovedajú farbám jednotlivých týchto štvorčekov. 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 obrazec

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) – to znamená pre „š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 (kde sa namiesto „štvorčekov” ofarbujú pixely) a podobne.

Základ programu

Funkciu na vyfarbovanie súvislých oblastí budeme dorábať do nasledujúcej kostry programu, ktorá 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. Nasledujúca kostra tiež obsahuje funkciu main, ktorá načíta maticu zo súboru vstup.txt a následne zatiaľ len vykreslí ňou reprezentovaný obrazec do súboru matica.svg.

#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

/* 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]);
        }
    }
}

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);

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

Rekurzívne vyfarbovanie

Vyfarbovanie súvislých oblastí potom môžeme realizovať napríklad nasledujúcou rekurzívnou funkciou vyfarbi, ktorá vždy na cieľovú farbu farba prefarbí políčko so súradnicami (riadok, stlpec) a následne sa rekurzívne zavolá pre všetkých susedov tohto políčka, ktoré sú zafarbené pôvodnou farbou prefarbovanej oblasti.

Za každým vyfarbením „štvorčeka” navyše voláme funkciu drawing.wait s parametrom pauza, čo je konštanta, ktorú na úvod nastavíme na 0,3 sekundy. Výsledný SVG súbor tak bude obsahovať animáciu postupného vyfarbovania jednotlivých políčok. Farbou „rámika” okolo políčka budeme navyše rozlišovať, či už bolo dané políčko úplne spracované (t. j. či sa už ukončilo rekurzívne volanie funkcie vyfarbi pre toto políčko).

const double pauza = 0.3;   // pauza po kazdom kroku vyfarbovania v sekundach

/* 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);
}

Funkcia main potom môže vyzerať napríklad nasledovne:

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);
}

• Výsledná animácia

Počítanie ostrovov

Obrazec, s ktorým sme pracovali vyššie, môže reprezentovať napríklad jednoduchú mapu súostrovia, kde more je znázornené modrou farbou a pevnina je znázornená žltou farbou. Úlohou môže byť zistiť počet ostrovov. Ten môžeme zistiť napríklad takto:

• Prechádzame postupne všetky políčka mapy.
• Ak narazíme na pevninu (t. j. žlté políčko), zvýšime doposiaľ nájdený počet ostrovov o 1 a ofarbíme celý ostrov (napríklad) na červeno.
• Ak narazíme na ďalšie žlté políčko, opäť urobíme to isté.
• Toto robíme, až kým prejdeme cez všetky políčka mapy.

Príklad mapy a jej zobrazenie pred začiatkom hľadania ostrovov, po nájdení prvých troch ostrovov a po nájdení všetkých ostrovov:

11 17
 1 1 1 1 1 1 3 1 1 1 1 1 1 1 1 1 1
 1 1 1 3 3 3 3 1 1 3 1 1 1 1 3 3 1
 1 1 1 3 3 1 1 1 1 1 1 1 1 1 3 3 1
 1 1 3 3 1 1 1 1 1 3 3 1 3 3 3 3 1
 1 1 1 3 3 1 1 1 1 3 1 1 3 3 3 3 1
 1 3 3 3 3 1 3 3 1 3 3 1 3 3 3 3 1
 1 1 3 3 1 1 1 3 1 1 1 1 1 1 1 1 1
 1 1 1 1 1 1 1 3 3 3 1 1 3 3 3 1 1
 1 1 1 1 1 1 1 3 3 3 1 1 3 1 3 1 1
 1 1 3 3 3 3 1 3 1 1 1 1 3 3 3 1 1
 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

• 
• 
• 

Do programu vyššie teda dorobíme funkciu

int najdiOstrovy(int **a, int m, int n, SVGdraw &drawing) {
    int ostrovov = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (a[i][j] == 3) {
                ostrovov++;
                vyfarbi(a, m, n, i, j, 4, drawing);
            }
        }
    }
    return ostrovov;
}

a funkciu main môžeme zmeniť napríklad takto:

int main() {
    FILE *fr = fopen("ostrovy.txt", "r");
    assert(fr != NULL);
    int m, n;
    fscanf(fr, "%d %d", &m, &n);
    int **a = vytvorMaticu(m, n);
    nacitajMaticu(fr, a, m, n);
    fclose(fr);
        
    SVGdraw drawing(n * stvorcek, m * stvorcek, "mapa.svg");
    vykresliMaticu(a, m, n, drawing);

    int pocetOstrovov = najdiOstrovy(a, m, n, drawing);
    printf("Pocet ostrovov je %d.\n", pocetOstrovov);

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

• Výsledná animácia

Cvičenie: upravte funkciu najdiOstrovy tak, aby ešte navyše zistila, či má niektorý z ostrovov jazero.

Vyfarbovanie s použitím zásobníka

S použitím niektorej implementácie zásobníka z minulej prednášky môžeme napísať aj nerekurzívnu verziu funkcie vyfarbi. Tá zakaždým vyberie zo zásobníka niektoré políčko. Ak ešte nebolo ofarbené, ofarbí ho a vloží na zásobník všetkých jeho susedov, ktorých je ešte potrebné ofarbiť.

Drobnou zmenou bude, že súradnice jednotlivých susedov budeme počítať s použitím cyklu for a polí deltaStlpec a deltaRiadok, ktoré pre i = 0,1,2,3 obsahujú posuny jednotlivých súradníc i-teho suseda oproti práve spracúvanému políčku.

struct policko {
    int riadok, stlpec;
};

typedef policko dataType;


/* Sem pride definicia struktury pre zasobnik 
 * a funkcii poskytovanych zasobnikom. */


const int deltaRiadok[4] = {0, 0, 1, -1};
const int deltaStlpec[4] = {1, -1, 0, 0};

/* 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;
    }
    
    stack s;
    init(s);
    
    policko p;
    p.riadok = riadok;
    p.stlpec = stlpec;
    push(s, p);
    
    while (!isEmpty(s)) {
        p = pop(s);
        if (a[p.riadok][p.stlpec] == farba) {
            // uz sme medzitym policko prefarbili z ineho smeru
            continue;
        }
        a[p.riadok][p.stlpec] = farba;
        vykresliStvorcek(p.riadok, p.stlpec, farby[farba], 
                         "lightgrey", drawing);
        drawing.wait(pauza);
        for (int i = 0; i <= 3; i++) {
            policko sused;
            sused.riadok = p.riadok + deltaRiadok[i];
            sused.stlpec = p.stlpec + deltaStlpec[i];
            if (sused.riadok >= 0 && sused.riadok < m
                && sused.stlpec >= 0 && sused.stlpec < n
                && a[sused.riadok][sused.stlpec] == staraFarba) {
                push(s, sused);    
            }        
        }
    }
    destroy(s);
}

• Výsledná animácia

Vyfarbovanie s použitím radu

Namiesto zásobníka môžeme použiť aj rad. Obrazec sa potom bude vyfarbovať v poradí podľa vzdialenosti od počiatočného políčka. Pôjde o takzvané prehľadávanie do šírky, kým rekurzívna verzia a verzia so zásobníkom zodpovedajú takzvanému prehľadávaniu do hĺbky.

struct policko {
    int riadok, stlpec;
};

typedef policko dataType;


/* Sem pride definicia struktury pre rad 
 * a funkcii poskytovanych radom. */


const int deltaRiadok[4] = {0, 0, 1, -1};
const int deltaStlpec[4] = {1, -1, 0, 0};

/* 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;
    }
    
    queue q;
    init(q);
    
    policko p;
    p.riadok = riadok;
    p.stlpec = stlpec;
    enqueue(q, p);
    
    while (!isEmpty(q)) {
        p = dequeue(q);
        if (a[p.riadok][p.stlpec] == farba) {
            continue;
        }
        a[p.riadok][p.stlpec] = farba;
        vykresliStvorcek(p.riadok, p.stlpec, farby[farba], 
                         "lightgrey", drawing);
        drawing.wait(pauza);
        for (int i = 0; i <= 3; i++) {
            policko sused;
            sused.riadok = p.riadok + deltaRiadok[i];
            sused.stlpec = p.stlpec + deltaStlpec[i];
            if (sused.riadok >= 0 && sused.riadok < m
                && sused.stlpec >= 0 && sused.stlpec < n
                && a[sused.riadok][sused.stlpec] == staraFarba) {
                enqueue(q, sused);    
            }        
        }
    }
    destroy(q);
}

• Výsledná animácia

Program potom môžeme upraviť aj tak, aby do každého ofarbeného políčka vypísal jeho vzdialenosť od počiatočného políčka:

struct policko {
    int riadok, stlpec, vzd;
};

typedef policko dataType;


/* Sem pride definicia struktury pre rad 
 * a funkcii poskytovanych radom. */


void vypisVzdialenost(int i, int j, int vzd, 
                      const char *farbaTextu, SVGdraw &drawing) {
    drawing.setLineColor(farbaTextu);
    drawing.setFontSize(20);
    char text[15];
    sprintf(text, "%d", vzd);
    drawing.drawText((j + 0.5) * stvorcek, (i + 0.5) * stvorcek, text);
}

const int deltaRiadok[4] = {0, 0, 1, -1};
const int deltaStlpec[4] = {1, -1, 0, 0};

/* 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;
    }
    
    queue q;
    init(q);
    
    policko p;
    p.riadok = riadok;
    p.stlpec = stlpec;
    p.vzd = 0;
    enqueue(q, p);
    
    while (!isEmpty(q)) {
        p = dequeue(q);
        if (a[p.riadok][p.stlpec] == farba) {
            continue;
        }
        a[p.riadok][p.stlpec] = farba;
        vykresliStvorcek(p.riadok, p.stlpec, farby[farba], 
                         "lightgrey", drawing);
        vypisVzdialenost(p.riadok, p.stlpec, p.vzd, 
                         "white", drawing);
        drawing.wait(pauza);
        for (int i = 0; i <= 3; i++) {
            policko sused;
            sused.riadok = p.riadok + deltaRiadok[i];
            sused.stlpec = p.stlpec + deltaStlpec[i];
            if (sused.riadok >= 0 && sused.riadok < m
                && sused.stlpec >= 0 && sused.stlpec < n
                && a[sused.riadok][sused.stlpec] == staraFarba) {
                sused.vzd = p.vzd + 1;
                enqueue(q, sused);    
            }        
        }
    }
    destroy(q);
}

• Výsledná animácia