Algorithm to divide a black-and-white chocolate bar

Question

Problem description: There's a chocolate bar that consists of m x n squares. Some of the squares are black, some are white. Someone breaks the chocolate bar along its vertical axis or horizontal axis. Then it is broken again along its vertical or horizontal axis and it's being broken until it can broken into a single square or it can broken into squares that are only black or only white. Using a preferably divide-and-conquer algorithm, find the number of methods a chocolate bar can be broken.

Input: The first line tells you the m x n dimensions of the chocolate bar. In the next m lines there are n characters that tell you how does the chocolate bar look. Letter w is a white square, letter b is a black square. for example: 3 2 bwb wbw

Output: the number of methods the chocolate bar can be broken: for the example above, it's 5 (take a look at the attached picture).

I tried to solve it using an iterative approach. Unfortunately, I couldn't finish the code as I'm not yet sure how to divide the the halves (see my code below). I was told that an recursive approach is much easier than this, but I have no idea how to do it. I'm looking for another way to solve this problem than my approach or I'm looking for some help with finishing my code.

I made two 2D arrays, first for white squares, second for black squares. I'm making a matrix out of the squares and if there's a chocolate of such or such color, then I'm marking it as 1 in the corresponding array. Then I made two arrays of the two cumulative sums of the matrices above. Then I created a 4D array of size [n][m][n][m] and I made four loops: first two (i, j) are increasing the size of an rectangular array that is the size of the searching array (it's pretty hard to explain...) and two more loops (k, l) are increasing the position of my starting points x and y in the array. Then the algorithm checks using the cumulative sum if in the area starting at position kxl and ending at k+i x l+j there is one black and one white square. If there is, then I'm creating two more loops that will divide the area in half. If in the two new halves there are still black and white squares, then I'm increasing the corresponding 4D array element by the number of combinations of the first halve * the number of combinations of the second halve.

    #include <iostream>
    #include <fstream>

    using namespace std;

    int main()
    {
        int counter=0;
        int n, m;
        ifstream in;
        in.open("in.txt");
        ofstream out;
        out.open("out.txt");
        if(!in.good())
        {
            cout << "No such file";
            return 0;
        }
        in >> n >> m;

        int whitesarray[m][n];
        int blacksarray[m][n];
        int methodsarray[m][n][m][n];

        for(int i=0; i<m; i++)
        {
            for(int j=0; j<n; j++)
            {
                whitesarray[i][j] = 0;
                blacksarray[i][j] = 0;
            }
       }

        while(in)
        {
            string colour;
            in >> colour;
            for (int i=0; i < colour.length(); i++)
            {
                if(colour[i] == 'c')
                {
                    blacksarray[counter][i] = 1;
                }
                if(colour[i] == 'b')
                {
                    whitesarray[counter][i] = 1;
                }
            }
            counter++;
        }

        int whitessum[m][n];
        int blackssum[m][n];


    for (int i=0; i<m; i++)
    {
        for (int j=0; j<n; j++)
        {
            if(i-1 == -1 && j-1 == -1)
            {
                whitessum[i][j] = whitesarray[i][j];
                blackssum[i][j] = blacksarray[i][j];
            }
            if(i-1 == -1 && j-1 != -1)
            {
                whitessum[i][j] = whitessum[i][j-1] + whitesarray[i][j];
                blackssum[i][j] = blackssum[i][j-1] + blacksarray[i][j];
            }
            if(j-1 == -1 && i-1 != -1)
            {
                whitessum[i][j] = whitessum[i-1][j] + whitesarray[i][j];
                blackssum[i][j] = blackssum[i-1][j] + blacksarray[i][j];

            }
            if(j-1 != -1 && i-1 != -1)
            {
                whitessum[i][j] = whitessum[i-1][j] + whitessum[i][j-1] - whitessum[i-1][j-1] + whitesarray[i][j];
                blackssum[i][j] = blackssum[i-1][j] + blackssum[i][j-1] - blackssum[i-1][j-1] + blacksarray[i][j];
            }
                }
    }


    int posx=0;
    int posy=0;
    int tempwhitessum=0;
    int tempblackssum=0;
    int k=0, l=0;

    for (int i=0; i<=m; i++)
    {
        for (int j=0; j<=n; j++) // wielkosc wierszy
        {
            for (posx=0; posx < m - i; posx++)
            {
                for(posy = 0; posy < n - j; posy++)
                {
            k = i+posx-1;
            l = j+posy-1;
            if(k >= m || l >= n)
                continue;
            if(posx==0 && posy==0)
            {
                tempwhitessum = whitessum[k][l];
                tempblackssum = blackssum[k][l];

            }
            if(posx==0 && posy!=0)
            {
                tempwhitessum = whitessum[k][l] - whitessum[k][posy-1];
                tempblackssum = blackssum[k][l] - blackssum[k][posy-1];

            }
            if(posx!=0 && posy==0)
            {
                tempwhitessum = whitessum[k][l] - whitessum[posx-1][l];
                tempblackssum = blackssum[k][l] - blackssum[posx-1][l];

            }
            if(posx!=0 && posy!=0)
            {
                tempwhitessum = whitessum[k][l] - whitessum[posx-1][l] - whitessum[k][posy-1] + whitessum[posx-1][posy-1];
                tempblackssum = blackssum[k][l] - blackssum[posx-1][l] - blackssum[k][posy-1] + blackssum[posx-1][posy-1];

            }
       if(tempwhitessum >0 && tempblackssum > 0)
       {
            for(int e=0; e<n; e++)
            {
                //Somehow divide the previously found area by two and check again if there are black and white squares in this area
            }
            for(int r=0; r<m; r++)
            {
                //Somehow divide the previously found area by two and check again if there are black and white squares in this area

            }
       }
                }
            }
        }}

        return 0;
    }

Answer 1

I strongly recommend recursion for this. In fact, Dynamic Programming (DP) would also be very useful, especially for larger bars. Recursion first ...

Recursion

Your recursive routine takes a 2-D array of characters (b and w). It returns the number of ways this can be broken.

First, the base cases: (1) if it's possible to break the given bar into a single piece (see my comment above, asking for clarification), return 1; (2) if the array is all one colour, return 1. For each of these, there's only one way for the bar to end up -- the way it was passed in.

Now, for the more complex case, when the bar can still be broken:

total_ways = 0
for each non-edge position in each dimension:
    break the bar at that spot; form the two smaller bars, A and B.
    count the ways to break each smaller bar: count(A) and count(B)
    total_ways += count(A) * count(B)
return total_ways

Is that clear enough for the general approach? You still have plenty of coding to do, but using recursion allows you to think of only the two basic ideas when writing your function: (1) How do I know when I'm done, and what trivial result do I return then? (2) If I'm not done, how do I reduce the problem?

---

Dynamic Programming

This consists of keeping a record of situations you've already solved. The first thing you do in the routine is to check your "data base" to see whether you already know this case. If so, return the known result instead of recomputing. This includes the overhead of developing and implementing said data base, probably a look-up list (dictionary) of string arrays and integer results, such as ["bwb", "wbw"] => 5.