Sposoby dzielenia czekolady.

Cześć,
muszę napisać program, który dla biało-czarnej czekolady o wymiarach NxM będzie ją dzielił na mniejsze kawałki. Dzielę do momentu gdy nowy kawałek zawiera tylko 2 kostki, a także każdy kawałek musi zawierać zarówno białą jak i czarną kostkę (tak jak na rysunku). Dzielenie czekolady realizuję rekurencyjnie, ale nie mam pomysłu w jaki sposób wykonać wszystkie możliwe podziały czekolady, aby uniknąć ich powtórzeń. Każdy wykorzystany sposób podziału dla każdej tabliczki powinienem zapisywać? Jeśli tak, to jak to wykonać dla tak wielu możliwości.

coś kojarzę, że to zadanie z: olimpiada informatyczna, SPOJ, main.edu.pl lub coś podobnego.
Zapodaj linka.

MarekR22 napisał(a):

coś kojarzę, że to zadanie z: olimpiada informatyczna, SPOJ, main.edu.pl lub coś podobnego.
Zapodaj linka.

W moim wypadku to zadanie na studia :D
Zadanie
Królewskie przyjęcie
Władca pewnego kraju co rok organizuje wielkie przyjęcie. Zapraszani są na nie wszyscy mieszkańcy: ze wsi i z miasta, bogaci i biedni. W czasie uroczystości nie brakuje jadła i picia – każdy gość jest bardzo zadowolony. W kraju tym wszyscy są entuzjastami czekolady, a specjalnie na przyjęcie przygotowywana jest duża, prostokątna tabliczka, którą dzieli się między wszystkich mieszkańców. Niektóre kawałki to są białe, a niektóre czarne. Pod koniec uroczystości król łamie wielką czekoladę na 2 kawałki – podział odbywa się wzdłuż jednej z poziomych lub pionowych bruzd. Następnie wręcza te dwa kawałki wybranym podwładnym, a ci dzielą je dalej w analogiczny sposób. Kiedy ktoś dostanie pojedynczy kawałek, to go zjada (ile można dzielić?). Dalszy podział nie jest również dokonywany, gdy jeden z powstałych fragmentów miałby być cały czarny lub cały biały (każdy gość chce zasmakować obu rodzajów). Wszyscy zauważyli, że dzielić czekoladę można na różne sposoby, a zależy to od doboru linii podziału tabliczki lub jej fragmentów. Król ogłosił konkurs: kto pierwszy powie, ile jest możliwych różnych podziałów czekolady w czasie uroczystości, ten otrzyma cenną nagrodę. Tym razem nie chodzi jednak o rękę królewny (król ma bowiem syna), ale o stanowisko królewskiego doradcy. Władca ceni sobie ludzi błyskotliwych. A czy Ty z pomocą komputera wygrałbyś konkurs?
Wejście:
W pierwszej linii wejścia podane są dwie liczby całkowite n i m (1<=n, m<=10) oznaczające odpowiednio długość i szerokość tabliczki czekolady. W kolejnych m liniach znajduje się po n znaków, które oznaczają rozkład kawałków białych i czarnych na tabliczce. Znak 'b' oznacza biały kawałek, a znak 'c' czarny kawałek.
Wyjście:
W jedynej linii wyjścia ma się znaleźć liczba sposobów podziału czekolady (modulo 109).
Przykład:
Wejście: 3 2
cbc
bcb Wyjście 5
//tabliczka czekolady o rozmiarze 3x2
//mamy 5 sposobów podziału (patrz rysunek)

najprościej wydaje się posortować rozwiązania – wtedy z łatwością znajdziesz identyczne i pousuwasz powtórzenia. Trzeba tylko znaleźć dobry, sortowalny sposób przestawienia podziału.

A jakiś pomysł w jaki sposób dla każdego kawałka wykorzystać wszystkie możliwości podziału?

to jest zadanie na rekurencję.

Masz to jakoś zaimplementowane? Tą tabliczkę czekolady, może jako macierz z zerami i jedynkami. Trzeba by opracować kod który dzieli i zwiększa licznik, po czym wywołuje funkcje rekurencyjnie od każdego kawałka, warunkiem brzegowym byłaby niemożliwość podziału - czyli mniej niż cztery elementy macierzy [chyba?].

def find_no_splits(matrix, cnt):
    if (/* tu warunek, number(matrix) < 4*/):
        return cnt
    // Dzielę macierz iteracyjnie, zwiekszam licznik i wywołuję
    //rekurencyjnie  od każdego kawałka

EDIT: Rozumiem, że nie można dzielić czekolady po łamanej?