[Algorytmy] Dzielenie czekolady na kawałki, rekurencja

[pred]

Witam.

Mam takie o to zdanie do rozwiązania. Koniecznie rekurencyjnie. Wiem, że trzeba zastosować podejście "dziel i zwyciężaj". Niestety nie wiem jak się za to za bardzo zabrać. Proszę o jakieś wskazówki, ew fragmenty kodu wedle czasowych możliwości.

Problem 1 - 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 \(\displaystyle{ n}\) i \(\displaystyle{ m}\) (\(\displaystyle{ 1 \le n, m \le 20}\)) oznaczające
odpowiednio długość i szerokość tabliczki czekolady. W kolejnych m liniach znajduje się po \(\displaystyle{ 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 \(\displaystyle{ 10^9}\)
).
Przykład:
Wejście:

Kod: Zaznacz cały

3 2 //tabliczka czekolady o rozmiarze 3x2
cbc
bcb

Wyjście

Kod: Zaznacz cały

5 //mamy 5 sposobów podziału (patrz rysunek)

rysunek wkleje później, jak serwer z zadankami zacznie działać)

[Afish]

Mając czekoladę o wymiarach \(\displaystyle{ x \times y}\) możesz dokonać maksymalnie \(\displaystyle{ x-1}\) cięć pionowych i \(\displaystyle{ y-1}\) cięć poziomych. Po każdym takim cięciu otrzymujesz dwie czekolady o mniejszych wymiarach. Liczba rozwiązań generowanych przez jedno cięcie to iloczyn liczby rozwiązań wygenerowanych mniejszych czekolad. Liczba rozwiązań dla kawałka to suma rozwiązań dla każdego cięcia, lub jedynka, jeżeli nie da się dzielić dalej.