Programovanie (1) v C/C++
1-INF-127, ZS 2025/26
Prednáška 1718
Obsah
Oznamy
- Dnešná prednáška je špeciálna z dvoch dôvodov:
- Hostia zo stredných škôl z programu Minierasmus
- V stredu prednáška nebude - fakultná konferencia Matfyz Connections
- Ukážeme si teda hrozienka z dvoch prednášok, zvyšok si pozrite vo videu
- Zajtra na cvičeniach rozcvička z minulej prednášky - čítanie súboru po riadkoch
- V stredu cvičenia nebudú
- Zverejníme aj jeden príklad z budúcich cvičení, môžete si spraviť v predstihu
- Tretí miniprojekt do budúceho štvrtka 4.12.
- Druhý semestrálny test streda 10.12. o 18:10
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 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);
}
Počítanie ostrovov
Vyfarbovanie teraz použijeme na riešenie trochu inej úlohy. Predstavme si, že vstupný obrázok reprezentuje 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 na mape. Ten môžeme zistiť napríklad takto:
- Prechádzame postupne všetky políčka mapy.
- Ak narazíme na pevninu (ž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);
}
Cvičenie: upravte program tak, aby ešte navyše zistil, či má niektorý z ostrovov jazero.
Opakovanie: 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)
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 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
Ďalší plán prednášky
- Pozrite si video s implementáciou zásobníka a radu pomocou polí a spájaných zoznamov
- Obidve implementácie sú jednoduché a rýchle, každá operácia je len pomocou zopár jednoduchých operácií
- Pozrite si video s použitím zásobníka na kontrolu zátvoriek
- Pozrite si video s použitím zásobníka alebo radu na nerekurzívny QuickSort
- Ukážeme si nerekurzívnu verziu vyfarbovania s použitím zásobníka alebo radu
- Čo sa nestihne budete mať tiež vo videu
Nerekurzívne vyfarbovanie
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, skontroluje všetkých jeho susedov a ak majú pôvodnú farbu, ofarbí ich a vloží ich na zásobník, aby sme ďalej skontrolovali aj ich susedov.
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 (dalo by sa použiť aj v rekurzívnej verzii).
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;
}
a[riadok][stlpec] = farba;
vykresliStvorcek(riadok, stlpec, farby[farba],
"lightgrey", drawing);
stack s;
init(s);
policko p;
p.riadok = riadok;
p.stlpec = stlpec;
push(s, p);
while (!isEmpty(s)) {
p = pop(s);
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) {
a[sused.riadok][sused.stlpec] = farba;
vykresliStvorcek(p.riadok, p.stlpec, farby[farba],
"lightgrey", drawing);
drawing.wait(pauza);
push(s, sused);
}
}
}
destroy(s);
}
- Výsledná animácia
- Poradie sa trochu zmenilo oproti rekurzívnej verzii. Prečo?
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. Tento algoritmus sa volá prehľadávanie do šírky, kým rekurzívna verzia zodpovedá 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;
}
a[riadok][stlpec] = farba;
vykresliStvorcek(riadok, stlpec, farby[farba],
"lightgrey", drawing);
queue q;
init(q);
policko p;
p.riadok = riadok;
p.stlpec = stlpec;
enqueue(q, p);
while (!isEmpty(q)) {
p = dequeue(q);
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) {
a[sused.riadok][sused.stlpec] = farba;
vykresliStvorcek(sused.riadok, sused.stlpec, farby[farba],
"lightgrey", drawing);
drawing.wait(pauza);
enqueue(q, sused);
}
}
}
destroy(q);
}
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(policko p, SVGdraw &drawing) {
drawing.setLineColor("white");
drawing.setFontSize(20);
char text[15];
sprintf(text, "%d", p.vzd);
drawing.drawText((p.stlpec + 0.5) * stvorcek,
(p.riadok + 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);
a[riadok][stlpec] = farba;
vykresliStvorcek(riadok, stlpec, farby[farba],
"lightgrey", drawing);
vypisVzdialenost(p, drawing);
while (!isEmpty(q)) {
p = dequeue(q);
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;
a[sused.riadok][sused.stlpec] = farba;
vykresliStvorcek(sused.riadok, sused.stlpec, farby[farba],
"lightgrey", drawing);
vypisVzdialenost(sused, drawing);
drawing.wait(pauza);
enqueue(q, sused);
}
}
}
destroy(q);
}
