Problém reprezentace obrázku binárním stromem (klikněte pro zobrazení zadání). Kromě kódu programu odevzdejte i výpis vstupů a výstupů pro všech 10 příkladů ve veřejném datasetu, na který je na konci zadání odkaz.

Nápověda řešení pro variantu minimálního počtu uzlů ve stromě:

Označím MU(x1, x2, y1, y2) minimální počet uzlů ve stromě reprezentujícím obraz mezi sloupci x1-x2 (včetně) a řádky y1-y2 (včetně). Například pro obdélník 2x3 v pravém horním rohu obrázku je to MU(W-2, W, 1, 2).

Teď lze napsat naivní algoritmus, který by řešil úlohu hrubou silou:

INPUT: char image[][];       // obrázek rozměrů HxW s hodnotami '0', '1'

// v tomto kódu ho používám jako globální proměnnou, i když se to nemá

int MU(int x1, int x2, int y1, int y2)  {

// metoda vrací počet uzlů v podstromu reprezentujícím výřez obrázku (obdélník)

// ve sloupcích x1 až x2 a řádcích y1 až y2 včetně

bool black = false;

bool white = false;

for (int i = x1; i <= x2; i++) {

     for (int j = y1; i <= y2; j++) {

         black |= image[i,j] == '1';

         white |= image[i,j] == '0';

     }

}

// pokud mají všechny pixly v obdélníku stejnou barvu, je výsledek 1

// obrázek je pak reprezentován grafem s jedním uzlem

if ! (black & white) {   return 1 }

// nastupuje dělení: v nejhorším případě budeme potřebovat pro každý pixel zvláštní list stromu

// celkový  počet uzlů ve stromě pak bude:

int vysledek = 2 * (x2 - x1+1) * (y2 - y1+1) - 1;

// vyzkoušíme všechna možná horizontální dělení a vybereme z nich nejlepší

for (int i = y1; i < y2; i++) {

     vysledek = Math.Min(vysledek, MU(x1, x2, y1, i) + MU(x1, x2, i+1, y2) + 1    }

// totéž pro vertikální dělení

for (int i = x1; i < x2; i++) {

     vysledek = Math.Min(vysledek, MU(x1, i, y1, y2) + MU(i+1, x2, y1, y2) + 1    }

return vysledek

}

Řešení úlohy dostanu zavoláním MU(0, W-1, 0, H-1).

Jaká je vada tohohle řešení? Že má exponenciální časovou složitost, to se dá snadno zjistit. Je to tak proto, že se různé mezivýsledky MU(x1, x2, y1, y2) pro stejnou kombinaci x1, x2, y1, y2 počítají opakovaně. Přitom, kolik je všech možných mezivýsledků, tj. všech možných obdélníků v obraze? Přesně W*(W+1)*H*(H+1)/4 (proč? zkuste odvodit).

Takže to chce algoritmus upravit - uchovávat někde potřebné mezivýsledky a postupně je počítat jako v úloze tabelace na slidech alg09, nebo při násobení matic na slidech alg10a na wiki stránkách ČVUT.