Stránka 1 z 1

Oliaty Koberec

PoslaťNapísal: Pon Júl 16, 2012 8:23 pm
od dzusik12
Viete mi niekto vysvetlit nejak hlavnu myslienku, ako zredukovat ulohu na ten "jednoduchy" strom, podla popisu riesenia ?
Autor návodu píše: "Náš program najprv pomocou DFS ofarbí každú oblasť jednou farbou, potom z nich urobí
strom a horeuvedeným spôsobom spočíta riešenie." Nerozumiem čo sa myslí prvou čaštou vety, ako ofarbí ?
Uloha http://www.ksp.sk/wiki/Zadania/Archiv
rocnik 28 priklad 6 ty, je tam aj navod na riesenie.

Re: Oliaty Koberec

PoslaťNapísal: Uto Júl 17, 2012 8:39 am
od bwpow
Proste hladaju komponenty grafu. Cely komponent "ofarbia" jednou farbou, ide len o obycajny zargon. Ako keby si mal obrazok toho koberca v paintbrushi a kazdy flak ofarbil inou farbou pomocou floodfillu, aby sa tie flaky dali vizualne dobre rozoznat od seba.

Re: Oliaty Koberec

PoslaťNapísal: Uto Júl 17, 2012 9:33 am
od FeroG
Alebo v PAZ1b terminológii :-), ak sa na fľaky pozrieš ako na bunky z úlohy o bunkách: pozadie dostane farbu 0, pixely prvej bunky (fľaku) farbu 1, pixely druhej bunky (fľaku) 2, atď. Čiže treba spraviť to, čo pri bunkách - akurát namiesto "vymazovania" pixelov bunky (fľaku) im priradíš "poradové" číslo fľaku.