dzielenie czekolady na mniejsze kawalki

0

Witam.

Zadanie próbowałem rozwiązać w ten sposób, ze zaczynam od ogółu i dzielę na mniejsze kawałki, przy tym sprawdzając ile jest czarnych/bialych kawałkow (musi byc minimum 1), lecz wydaje mi sie to słabym rozwiązaniem, poza tym coś dobrze nie działa.

Treść:
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 n i m (1<=n, m<=20) 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 10^9
).
Przykład:
Wejście:
3 2 //tabliczka czekolady o rozmiarze 3x2
cbc
bcb
Wyjście
5 //mamy 5 sposobów podziału (patrz rysunek - rysunek wkleje później, jak serwer z zadankami zacznie działać, na razie rysunek własnoręczny zapodaj.net/0e816eda97984.jpg.html)

Oczywiście nie liczę na gotowy kod (ale też nie pogardzę jeśli komuś sie nudzi :) ), lecz na jakieś wskazówki co i gdzie mam szukać. Wiem, że trzeba zastosować podejści "Dziel i zwyciężaj" lecz nie mam pomysłu jak to poprawnie zaimplementować. Algorytm trzeba rozwiązać koniecznie rekurencyjnie. (wymóg zadania)

0

Zdefiniuj "liczba sposobów podziału czekolady"!
Do jednego układu kawałków można dojść na wiele sposobów.
Najprostszy przykład:

bc
cb

Najpierw można koić poziomo a potem pionowo, albo na odwrót. Czy to znaczy, że prawidłowa odpowiedź to 2 czy 1?

1 użytkowników online, w tym zalogowanych: 0, gości: 1