划分 black-and-white 巧克力棒的算法

Question

问题描述：有一块巧克力，由 m x n 个方块组成。有些方块是黑色的，有些是白色的。有人沿着垂直轴或水平轴打破巧克力棒。然后它沿着它的垂直或水平轴再次被打破，它被打破直到它可以被打破成一个单一的正方形或者它可以被打破成只有黑色或只有白色的正方形。使用 preferred divide-and-conquer 算法，求出可以打破巧克力块的方法数。

输入：第一行告诉您巧克力块的 m x n 尺寸。在接下来的 m 行中，有 n 个字符告诉您巧克力棒的外观。字母w是白色方块，字母b是黑色方块。例如： 3 2 体重秤 wbw

输出：可以打破巧克力棒的方法数：对于上面的例子，它是 5（看附图）。

我尝试使用迭代方法解决它。不幸的是，我无法完成代码，因为我还不确定如何划分两半（请参阅下面的代码）。有人告诉我递归方法比这容易得多，但我不知道该怎么做。我正在寻找另一种方法来解决这个问题，而不是我的方法，或者我正在寻找一些帮助来完成我的代码。

我制作了两个二维数组，第一个用于白色方块，第二个用于黑色方块。我正在用正方形制作一个矩阵，如果有这种或这种颜色的巧克力，那么我会在相应的数组中将其标记为 1。然后我做了两个上面矩阵的两个累加和的数组。然后我创建了一个大小为 [n][m][n][m] 的 4D 数组，并做了四个循环：前两个 (i, j) 增加了矩形数组的大小，即搜索数组的大小 (这很难解释......）并且另外两个循环（k，l）正在增加我的起点 x 和 y 在数组中的位置。然后算法使用累积和检查在从位置 kxl 开始到 k+i x l+j 结束的区域中是否有一个黑色和一个白色方块。如果有，那么我将再创建两个将区域分成两半的循环。如果在新的两半中仍然有黑白方块，那么我将相应的 4D 数组元素增加前半部分的组合数 * 后半部分的组合数。

    #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

我强烈建议为此使用递归。事实上，动态规划 (DP) 也非常有用，尤其是对于较大的柱。递归优先...

递归

您的递归例程采用二维字符数组（b 和 w）。它 return 有多少种方法可以破坏它。

首先，基本情况：(1) 如果有可能将给定的条分解成一个单一的部分（请参阅我上面的评论，要求澄清），return 1； (2) 如果数组都是一种颜色，return 1. 对于其中的每一个，条形图只有一种结束方式——传入的方式。

现在，对于更复杂的情况，当柱仍然可以被打破时：

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

通用方法是否足够清楚？您仍然有很多编码工作要做，但是使用递归可以让您在编写函数时只考虑两个基本思想：(1) 我怎么知道我什么时候完成了，我会得到什么微不足道的结果 return 然后？ (2) 如果我没有完成，我该如何减少问题？

动态规划

这包括记录您已经解决的情况。你在例程中做的第一件事是检查你的 "data base" 看看你是否已经知道这种情况。如果是这样，return 已知结果而不是重新计算。这包括开发和实施所述数据库的开销，可能是字符串数组和整数结果的查找列表（字典），例如 ["bwb", "wbw"] => 5.

划分 black-and-white 巧克力棒的算法

Algorithm to divide a black-and-white chocolate bar

c++

algorithm

recursion

divide-and-conquer