Prednáška 18

Rad pomocou spájaného zoznamu

Pri implementácii radu pomocou spájaného zoznamu rozšírime spájané zoznamy zo 14. prednášky o smerník last na posledný prvok zoznamu. Bude tak možné jednoducho vkladať prvky na koniec zoznamu, ako aj odoberať prvky zo začiatku zoznamu.

Výhodou oproti implementácii radu pomocou poľa bude, podobne ako pri zásobníkoch, eliminácia obmedzenia na maximálny počet prvkov v rade.

#include <cassert>

// ...

struct node {
    dataType data;
    node *next;
};

struct queue {
    node *first; // Smernik na prvy prvok radu (spajaneho zoznamu). Ak je rad prazdny, ma hodnotu NULL.
    node *last;  // Smernik na posledny prvok radu (spajaneho zoznamu). Ak je rad prazdny, ma hodnotu NULL.
};

/* Inicializuje prazdny rad */
void init(queue &q) {
    q.first = NULL;
    q.last = NULL;
}

/* Zisti, ci je rad prazdny */
bool isEmpty(queue &q) {
    return q.first == NULL;
}

/* Prida prvok item na koniec radu */
void enqueue(queue &q, dataType item) {
    node *tmp = new node;
    tmp->data = item;
    tmp->next = NULL;
    if (isEmpty(q)) {
        q.first = tmp;
        q.last = tmp;
    } else {
        q.last->next = tmp;
        q.last = tmp;
    }
} 

/* Odoberie prvok zo zaciatku radu a vrati jeho hodnotu */
dataType dequeue(queue &q) {
    assert(!isEmpty(q));
    dataType result = q.first->data;
    node *tmp = q.first->next;
    delete q.first;
    if (tmp == NULL) {
        q.first = NULL; 
        q.last = NULL;
    } else {
        q.first = tmp;
    } 
    return result;
}

/* Vrati prvok zo zaciatku radu, ale necha ho v rade */
dataType peek(queue &q) {
    assert(!isEmpty(q));
    return q.first->data;
}         

/* Uvolni pamat */
void destroy(queue &q) {
    while (!isEmpty(q)) {
        dequeue(q);
    }
}

Použitie zásobníka a radu

Zásobník aj rad často uchovávajú dáta určené na spracovanie, zoznamy úloh, atď. Rad sa zvyčajne používa v prípadoch, keď je žiadúce zachovať ich poradie. Typicky môže ísť o situácie, keď jeden proces generuje úlohy spracúvané iným procesom, napríklad:

• Textový procesor pripravuje strany na tlač a vkladá ich do radu, z ktorého ich tlačiareň (resp. jej ovládač) postupne vyberá.
• Sekvenčne vykonávané výpočtové úlohy čakajú v rade na spustenie.
• Zákazníci čakajú na zákazníckej linke na voľného operátora.
• Pasažieri na standby čakajú na voľné miesto v lietadle.

Zásobník sa, ako o niečo implementačne jednoduchší koncept, zvyčajne používa v situáciách, keď na poradí spracúvania nezáleží, alebo keď je žiadúce vstupné poradie obrátiť. Najvýznamnejší príklad situácie druhého typu je nasledujúci:

• Operačný systém ukladá lokálne premenné volaných funkcií na tzv. zásobníku volaní (angl. call stack), čo umožňuje používanie rekurzie.
• Rekurzívne programy sa dajú prepísať na nerekurzívne pomocou „ručne vytvoreného” zásobníka (na budúcej prednáške si ako príklad ukážeme nerekurzívnu verziu triedenia Quick Sort).

Príklad: kontrola uzátvorkovania

Ako jednoduchý príklad na použitie zásobníka uvažujme nasledujúcu situáciu: na vstupe je daný reťazec pozostávajúci (okrem prípadných ďalších znakov, ktoré možno ignorovať) zo zátvoriek (,),[,],{,}. Úlohou je zistiť, či je tento reťazec dobre uzátvorkovaný. To znamená, že:

• Pre každú uzatváraciu zátvorku musí byť posledná dosiaľ neuzavretá otváracia zátvorka rovnakého typu, pričom musí existovať aspoň jedna dosiaľ neuzavretá zátvorka.
• Každá otváracia zátvorka musí byť niekedy neskôr uzavretá.

Príklady očakávaného vstupu a výstupu:

()
Retazec je dobre uzatvorkovany

nejaky text bez zatvoriek
Retazec je dobre uzatvorkovany

[((({}[])[]))]()
Retazec je dobre uzatvorkovany

[[#))
Retazec nie je dobre uzatvorkovany

())(
Retazec nie je dobre uzatvorkovany

((
Retazec nie je dobre uzatvorkovany

((cokolvek
Retazec nie je dobre uzatvorkovany

Túto úlohu rieši nasledujúci program, ktorý postupne prechádza cez vstupný reťazec, pričom pre každú otváraciu zátvorku si na zásobník pridá uzatváraciu zátvorku rovnakého typu. Ak narazí na uzatváraciu zátvorku, výraz môže byť dobre uzátvorkovaný len v prípade, že je na zásobníku aspoň jedna zátvorka, pričom zátvorka na vrchu zásobníka sa zhoduje so zátvorkou na vstupe. V prípade úspešného prechodu cez celý vstup je reťazec dobre uzátvorkovaný práve vtedy, keď na zásobníku nezostala žiadna zátvorka.

#include <iostream>
#include <cassert>
using namespace std;

typedef char dataType;

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

int main(void) {
    char vyraz[100];
    cin.getline(vyraz, 100);
    
    stack s;
    init(s);
    
    bool dobre = true;
    
    for (int i = 0; vyraz[i] != 0; i++) {
        switch (vyraz[i]) {
            case '(':
                push(s, ')');
                break;
            case '[':
                push(s, ']');
                break;
            case '{':
                push(s, '}');
                break;
            case ')':
            case ']':
            case '}':
                if (isEmpty(s)) {
                    dobre = false;
                } else {
                    char c = pop(s);
                    if (c != vyraz[i]) {
                        dobre = false;
                    }
                }
                break;
        }
    }
    
    dobre = dobre && isEmpty(s);
        
    destroy(s);
    
    if (dobre) {
        cout << "Retazec je dobre uzatvorkovany." << endl;
    } else {
        cout << "Retazec nie je dobre uzatvorkovany." << endl;
    }
    
    return 0;
}

Cvičenie: Prepíšte program na kontrolu zátvoriek do rekurzívnej podoby. Použite pritom iba premenné typu char; špeciálne nepoužívajte žiadne polia. Reťazec načítavajte pomocou funkcií getc a ungetc. Môžete predpokladať, že je ukončený koncom riadku.

Príklad: 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 low, int high) {
    int pivot = a[low];
    int lastSmaller = low;
    
    for (int unknown = low + 1; unknown <= high; unknown++) {
        if (a[unknown] < pivot) {
            lastSmaller++;
            swap(a[unknown], a[lastSmaller]);
        }
    }   
    swap(a[low],a[lastSmaller]); 
    return lastSmaller;
}

void quicksort(int a[], int low, int high) {
    if (low >= high) {
        return;
    }
    
    int mid = partition(a, low, high);
        
    quicksort(a, low, mid-1);
    quicksort(a, mid+1, high);   
}

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

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

struct usek {
    int low;
    int high;
};

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.low = 0;
    u.high = n-1;
    push(s,u);
    
    while (!isEmpty(s)) {
        u = pop(s);
        if (u.low >= u.high) {
            continue;
        }
        
        int mid = partition(a, u.low, u.high);
        
        usek u1;
        u1.low = u.low;
        u1.high = mid-1;
        usek u2;
        u2.low = mid+1;
        u2.high = u.high;
        push(s,u2);
        push(s,u1);
    }
    
    destroy(s);
}

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

Tento program triedi úseky v rovnakom poradí, ako rekurzívny Quicksort, 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í.

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 - 1; i++) {
        a[i] = new int[n];
    }
    return a;
}

/* Uvolni pamat matice a s n riadkami a m stlpcami. */
void zmazMaticu(int m, int n, int **a) {
    for (int i = 0; i <= m - 1; 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 m, int n, int **a, SVGdraw &drawing) {
    for (int i = 0; i <= m - 1; i++) {
        for (int j = 0; j <= n - 1; 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 m, int n, int **a) {
    assert(fr != NULL);
    for (int i = 0; i <= m - 1; i++) {
        for (int j = 0; j <= n - 1; j++) {
            fscanf(fr, "%d", &a[i][j]);
        }
    }
}

int main(void) {
    FILE *fr = fopen("vstup.txt", "r");
    assert(fr != NULL);
    int m, n;
    fscanf(fr, "%d", &m);               // nacitaj rozmery matice
    fscanf(fr, "%d", &n);
    int **a = vytvorMaticu(m, n);
    nacitajMaticu(fr, m, n, a);         // nacitaj jednotlive prvky matice
    fclose(fr);
        
    SVGdraw drawing(n * stvorcek, m * stvorcek, "matica.svg");
    vykresliMaticu(m, n, a, drawing);

    drawing.finish();
    zmazMaticu(m, n, a);
    
    return 0;
}

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 vysvetlovania v sekundach

/* Prefarbi suvislu jednofarebnu oblast obsahujucu poziciu (riadok,stlpec) na farbu s cislom farba. */
void vyfarbi(int m, int n, int **a, 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(m, n, a, riadok - 1, stlpec, farba, drawing);
    }
    if (riadok + 1 <= m - 1 && a[riadok + 1][stlpec] == staraFarba) {
        vyfarbi(m, n, a, riadok + 1, stlpec, farba, drawing);
    }
    if (stlpec - 1 >= 0 && a[riadok][stlpec - 1] == staraFarba) {
        vyfarbi(m, n, a, riadok, stlpec - 1, farba, drawing);
    }
    if (stlpec + 1 <= n - 1 && a[riadok][stlpec + 1] == staraFarba) {
        vyfarbi(m, n, a, 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(void) {
    FILE *fr = fopen("vstup.txt", "r");
    assert(fr != NULL);
    int m, n;
    fscanf(fr, "%d", &m);               // nacitaj rozmery matice
    fscanf(fr, "%d", &n);
    int **a = vytvorMaticu(m, n);
    nacitajMaticu(fr, m, n, a);         // nacitaj jednotlive prvky matice
    fclose(fr);
        
    SVGdraw drawing(n * stvorcek, m * stvorcek, "matica.svg");
    vykresliMaticu(m, n, a, drawing);

    int riadok, stlpec;
    scanf("%d", &riadok);
    scanf("%d", &stlpec);

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

    drawing.finish();
    zmazMaticu(m, n, a);
    
    return 0;
}

• 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 z vyššia teda dorobíme funkciu

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

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

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

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

    drawing.finish();
    zmazMaticu(m, n, a);
    
    return 0;
}

• 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 m, int n, int **a, 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) {
            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 - 1 && sused.stlpec >= 0 && sused.stlpec <= n - 1 &&
                    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 m, int n, int **a, 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 - 1 && sused.stlpec >= 0 && sused.stlpec <= n - 1 &&
                    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 m, int n, int **a, 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];
            sused.vzd = p.vzd + 1;
            if (sused.riadok >= 0 && sused.riadok <= m - 1 && sused.stlpec >= 0 && sused.stlpec <= n - 1 &&
                    a[sused.riadok][sused.stlpec] == staraFarba) {
                enqueue(q, sused);    
            }        
        }
    }
    destroy(q);
}

• Výsledná animácia