recursion - Algorithm to divide black and white chocolate bar with least number of breaks

Question

I have a rectangular chocolate bar that consists of squares either black, white or mixed. The bar being not bigger than 50x50 squares. I'm supposed to divide the bar between two people(one gets all the white squares and one the black ones, mixed ones don't matter), by cracking it either horizontally or vertically. I'm supposed to find a method with the least amount of such cracks.

I'm given this input:

M N (number of rows, number of columns) and then M rows that are N numbers long(0 means white, 1 means black, 2 is mixed) so for example bar described like this:

4 4
0 1 1 1
1 0 1 0
1 0 1 0
2 0 0 0

can be divided by cracking it seven times in total.

And this one needs at least 24 cracks:

5 8
0 1 0 1 0 1 0 2
1 0 2 0 2 0 1 0
0 2 0 2 0 1 0 2
1 0 2 0 2 0 1 0
0 1 0 1 0 1 0 2

I was thinking about something like cracking the bar in two pieces so that the sum of sums of future cracks needed to divide two newly made chocolate bar pieces is the least possible from all the possible cracks (which is height -1 + width -1 of the current bar piece being cracked)

I managed, also thanks to zenwraight, to write a code that solves this but I encountered another problem, it is really inefficient and if the starting chocolate bar gets bigger than 30x30 it's practically unusable. Anyway the source code (written in C):

#include <stdio.h>
#include <stdlib.h>

const int M, N;
int ****pieces;
int r = 0;
int ri = 0;
int inf;

void printmatrix(int **mat, int starti, int startj, int maxi, int maxj) {
    for (int i = starti; i < maxi; i++) {
        for (int j = startj; j < maxj; j++) {
            printf("%d ", mat[i][j]);
        }
        printf("
");
    }
}

int minbreaks(int **mat, int starti, int startj, int maxi, int maxj, int depth) {
    if (pieces[starti][startj][maxi][maxj] != 0) {
        r++;
        return pieces[starti][startj][maxi][maxj];
    } else {
        ri++;
        int vbreaks[maxj - 1];
        int hbreaks[maxi - 1];
        for (int i = 0; i < maxj; i++) {
            vbreaks[i] = inf;
        }
        for (int i = 0; i < maxi; i++) {
            hbreaks[i] = inf;
        }
        int currentmin = inf;
        for (int i = starti; i < maxi; i++) {
            for (int j = startj; j < maxj - 1; j++) {//traverse trough whole matrix
                if (mat[i][j] != 2) {
                    for (int k = startj + 1; k < maxj; k++) {//traverse all columns
                        if (vbreaks[k - 1] == inf) {//traverse whole column
                            for (int z = starti; z < maxi; z++) {
                                if (mat[z][k] != 2 && mat[i][j] != mat[z][k]) {
                                    /* printmatrix(mat, starti, startj, maxi, maxj);
                                     printf("brokenv in depth:%d->
", depth);
                                     printmatrix(mat, starti, startj, maxi, k);
                                     printf("and
");
                                     printmatrix(mat, starti, k, maxi, maxj);
                                     printf("****
");*/
                                    vbreaks[k - 1] = minbreaks(mat, starti, startj, maxi, k, depth + 1) + minbreaks(mat, starti, k, maxi, maxj, depth + 1);
                                    if (vbreaks[k - 1] < currentmin) {
                                        currentmin = vbreaks[k - 1];
                                    }
                                    break;
                                }
                            }
                        }
                    }
                }
            }
        }
        for (int i = starti; i < maxi - 1; i++) {
            for (int j = startj; j < maxj; j++) {
                if (mat[i][j] != 2) {
                    for (int k = starti + 1; k < maxi; k++) {
                        if (hbreaks[k - 1] == inf) {
                            for (int z = startj; z < maxj; z++) {
                                if (mat[k][z] != 2 && mat[i][j] != mat[k][z]) {
                                    /* printmatrix(mat, starti, startj, maxi, maxj);
                                     printf("brokenh in depth:%d->
", depth);
                                     printmatrix(mat, starti, startj, k, maxj);
                                     printf("and
");
                                     printmatrix(mat, k, startj, maxi, maxj);
                                     printf("****
");*/
                                    hbreaks[k - 1] = minbreaks(mat, starti, startj, k, maxj, depth + 1) + minbreaks(mat, k, startj, maxi, maxj, depth + 1);
                                    if (hbreaks[k - 1] < currentmin) {
                                        currentmin = hbreaks[k - 1];
                                    }
                                    break;
                                }
                            }
                        }
                    }
                }
            }
        }
        if (currentmin == inf) {
            currentmin = 1;
        }
        pieces[starti][startj][maxi][maxj] = currentmin;
        return currentmin;
    }
}

void alloc(int i, int j) {
    pieces[i][j] = malloc(sizeof (int*)*(M + 1));
    for (int y = i; y < M + 1; y++) {
        pieces[i][j][y] = malloc(sizeof (int)*(N + 1));
        for (int x = j; x < N + 1; x++) {
            pieces[i][j][y][x] = 0;
        }
    }
}

int main(void) {
    FILE *file = fopen("pub08.in", "r");
    //FILE *file = stdin;
    fscanf(file, "%d %d", &M, &N);
    int **mat = malloc(sizeof (int*)*M);
    pieces = malloc(sizeof (int***)*M);
    for (int i = 0; i < M; i++) {
        mat[i] = malloc(sizeof (int)*N);
        pieces[i] = malloc(sizeof (int**)*N);
        for (int j = 0; j < N; j++) {
            int x;
            fscanf(file, "%d", &x);
            mat[i][j] = x;
            alloc(i, j);
        }
    }
    inf = M * (M + 1) * N * (N + 1) / 4 + 1;
    int result = minbreaks(mat, 0, 0, M, N, 0);
    printf("%d
", result);
    printf("ri:%d,r:%d
", ri, r);
    return (EXIT_SUCCESS);
}

I am aiming to solve this input :

40 40
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 2 2 1 2 1 1 0 0 0 0 0 0 0 0 0 0
0 0 0 1 1 1 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 1 1 1 0 0 0 0 0 0 0 0 0 0
0 0 0 1 1 1 0 2 1 2 1 2 0 0 1 2 2 0 0 0 0 0 0 0 0 1 1 2 1 2 0 0 0 0 0 0 0 0 0 0
0 0 0 1 2 2 0 1 1 1 1 1 0 0 1 2 2 0 0 0 0 0 1 0 0 2 2 1 1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 2 2 1 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1 1 2 2 0 0 0 1 2 2 1 2 1 0 0 0 0 0 1 2 1 2 0 0 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 2 2 1 2 0 0 0 0 0 2 1 2 2 0 0 0 0 0 2 1 2 1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 2 2 2 1 1 0 0 0 0 0 2 1 1 1 0 0 0 0 0 0 0 0 0 0 0 1 2 1 0 0 0 0 0 0
0 2 1 2 1 0 2 2 2 2 1 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 2 2 1 2 0 2 2 1 0 0 0 0 0 0
0 2 2 1 2 0 1 2 2 1 1 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 1 0 0 0 0 0 0
0 2 2 1 2 0 0 0 0 2 1 2 1 2 1 1 2 0 2 0 0 0 0 0 0 0 1 2 2 2 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 2 2 2 2 1 2 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0
0 0 0 0 0 0 0 0 0 1 2 1 1 2 2 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 2 2 0 0 0 0
0 0 0 0 0 0 0 2 1 2 0 0 2 2 1 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 2 1 1 0 0 0 0
0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 2 2 0 0 0 0
0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 1 2 2 1 0 0 0 0 2 0 1 1 1 2 1 2 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 2 0 0 0 0 0 0 2 1 2 2 2 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 2 0 0 0 0 0 0 1 2 1 1 2 2 0 0 0 0 0
0 0 0 0 0 0 1 2 1 2 2 1 0 0 0 0 0 0 0 1 2 1 2 0 0 0 0 0 0 0 0 0 2 1 2 0 0 0 0 0
0 0 0 0 0 0 1 2 2 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 2 0 0 0 0 0 0 0 0 0 0 2 1 1 0 0
0 0 0 0 0 0 1 1 1 1 1 2 2 0 0 0 0 0 0 0 0 1 1 1 2 0 0 0 0 0 0 0 0 0 0 1 2 1 0 0
0 0 0 0 0 0 1 2 2 2 1 1 1 0 0 0 0 0 0 0 0 1 2 1 2 0 0 0 0 0 0 0 0 0 0 2 2 2 1 0
0 0 0 0 0 0 0 0 0 1 2 1 2 0 0 0 0 0 0 0 0 1 1 1 2 2 0 0 0 0 0 0 0 0 0 1 2 1 1 0
0 0 0 2 1 1 2 2 0 1 2 1 1 0 0 0 0 0 2 2 1 2 2 1 2 2 0 0 0 0 0 0 0 0 0 1 2 2 2 0
0 0 0 2 2 2 1 1 0 0 1 2 2 2 0 0 0 0 2 2 2 1 1 2 1 1 2 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 2 1 2 2 1 1 0 2 1 2 1 2 1 2 1 1 2 1 1 1 1 1 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 2 2 2 2 1 0 1 1 1 1 1 1 2 1 1 2 2 1 0 1 2 1 2 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 1 1 0 0 2 1 1 1 2 1 2 0 0 1 2 1 2 1 2 2 0 0 0 0 0 0 0 1 1 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 1 2 2 1 1 2 2 1 1 1 1 1 1 1 2 1 0 0 0 0 0 0 0 2 2 2 0 0 0
0 0 0 0 0 0 0 1 1 1 2 0 0 1 1 1 2 2 1 2 2 2 1 0 0 0 1 1 1 0 0 0 0 0 1 2 1 0 0 0
0 0 0 0 0 0 0 2 1 1 2 0 0 0 0 0 0 2 2 2 1 1 1 0 0 0 1 2 2 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 2 2 2 2 0 0 0 0 0 0 2 1 1 1 2 0 0 0 0 1 2 2 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 2 2 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 1 1 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 1 0 0 0 0 0 0 0 1 1 2 0 2
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 2 2 2 0 0 0 0 0 0 0 1 2 1 0 0
0 0 0 0 0 0 0 0 0 2 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 2 2 2 0 0 0 0 0 0 0 1 2 1 0 0
0 0 0 0 0 0 0 0 0 2 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1 1 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

in under 2 seconds, which is much much faster time than that of my current program. The minimum amount of cracks for this one is 126.

Answer 1

Nice question, I have an approach in mind which makes use of recursion to tackle the above problem.

So as at each level or step you have two options either to split the bar horizontally or vertically.

So let's understand the algorithm with an example.

Example:-

4 4
0 1 1 1
1 0 1 0
1 0 1 0
2 0 0 0

Now let's call our function minBreaks(int n, int m, int matleft, int right)

So at first step if we break is horizontally our matleft will be

0
1
1
2

and matright will be

1 1 1
0 1 0
0 1 0
0 0 0

Now similarly if we had broken this vertically our matleft will be

0 1 1 1

and matright will be

1 0 1 0
1 0 1 0
2 0 0 0

Now you pass along this matleft and matright in next recursion call

And then at each call when size of row = 1 or col = 1, you can check the connected components of same value and return the count of connected components

Like for example for vertically case of maxleft -> 0 1 1 1, you will return 2.

Similarly for all the cases and the end part of the method will return

min between break horizontally and vertically

Hope this helps!