Try to break chocolate into black and white pieces using minimal ammount of breakings

chocolate.cpp

//TASK: https://cw.felk.cvut.cz/courses/a4b33alg/task.php?task=chocolate

#include <iostream>
#include <vector>

using namespace std;
#ifdef WIN32

int getchar_unlocked() { return getchar(); }

#elif UNIX
/* Do linux stuff */
#endif

struct My4DArray
{
    My4DArray(){}
    My4DArray(int d1, int d2, int d3, int d4) :
            d1(d1), d2(d2), d3(d3), d4(d4), data(d1*d2*d3*d4,0) {}

    unsigned int& at(int i1, int i2, int i3, int i4)
    {
        return data[getIndex(i1, i2, i3, i4)];
    }

    int getIndex(int i1, int i2, int i3, int i4)
    {
        return (((i1*d2 + i2)*d3 + i3)*d4 + i4);
    }

    void write(int i1, int i2, int i3, int i4, unsigned int toWrite){
        data[getIndex(i1, i2, i3, i4)] = toWrite;
    }

    int d1;
    int d2;
    int d3;
    int d4;
    std::vector<unsigned int> data;

};

vector<vector<int>> bar;
My4DArray cache;

static inline void scanint(int &x) {
    // fastest stdin reading, found on https://stackoverflow.com/questions/27899413/understanding-getchar-unlocked
    register int c = getchar_unlocked();
    x = 0;
    for (; (c < 48 || c > 57); c = getchar_unlocked());
    for (; c > 47 && c < 58; c = getchar_unlocked()) {
        x = (x << 1) + (x << 3) + (c & 15);
    }
}

unsigned int choco(int x1, int y1, int x2, int y2) {
    //TODO CACHE
    if(cache.at(x1,y1,x2,y2) != 0)
        return cache.at(x1,y1,x2,y2);

    bool white = false;
    bool black = false;

    //check monochromatic
    for (int x = x1; x <= x2; ++x) {
        for (int y = y1; y <= y2; ++y) {
            if (bar[y][x] == 1)
                white = true;
            else if (bar[y][x] == 0)
                black = true;
        }
    }

    //monochormatic - no braking
    if (!(white && black))
    {
        cache.write(x1,y1,x2,y2,1);
        return 1;//TODO CaChE
    }

    unsigned int slaps = INT32_MAX;
    for (int i = x1; i < x2; i++) { //try to break col and then tr to recursively break other side of chocolate
        //aka move vertical splitting line ot the right
        unsigned int splited = choco(x1, y1, i, y2) + choco(i + 1, y1, x2, y2);
        if (slaps > splited)
            slaps = splited;
    }

    for (int i = y1; i < y2; ++i) {
        unsigned int splited = choco(x1, y1, x2, i) + choco(x1, i + 1, x2, y2);
        if (slaps > splited)
            slaps = splited;
    }

    cache.write(x1,y1,x2,y2,slaps);
    return slaps;//TODO ADD CACHE
}

int main() {
    int width, height;
    scanint(height);
    scanint(width);

    bar.resize(height,vector<int>(width));
    cache = My4DArray(width,height,width,height);

    for (int y = 0; y < height; ++y) {
        for (int x = 0; x < width; ++x) {
            int color;
            scanint(color);
            bar[y][x] = color;
        }
    }
    int result = choco(0, 0, width - 1, height - 1);
    printf("%d\n", result);
    return 0;
}