在矩形巧克力棒中寻找最小数量的矩形块，有一个规则。

Question

我在学校的作业中遇到了困难。我有一块巧克力棒，由黑色、白色或黑白相间的正方形组成。我需要将它分为两组，一组只有白色或黑白相间的块，另一组只有黑色或黑白相间的块。将巧克力棒分开意味着沿着分离单个正方形的线条水平或垂直地将其破裂。

给定巧克力棒的布局，我需要找到一种最佳分割方式，将暗色和白色立方体分开，并得到可能的最小碎片数，巧克力棒不大于50x50个正方形。

巧克力棒在标准输入上定义如下：第一行由两个整数M（巧克力棒中的行数）和N（列数）组成，然后有M列，每列包含N个字符，表示各个正方形（0-黑色，1-白色，2-混合）。

以下是一些最佳分割的示例，它们的输入分别是（正确输出为3和7）：

3 3
1 1 2
1 2 0
2 0 0

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

我的问题是，我已经找到了一种解决方案，但我使用的算法不够快，如果巧克力条很大，比如这个例子：

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

然后我的程序需要10秒钟才能解决它（正确的解决方案为126，我应该能在2秒内解决它！）

我的算法大致如此，经过一些小的优化：迭代所有可能的切割线，然后对于新出现的2个矩形递归执行相同的操作，如果它们不能再分割，则返回1。

在迭代完所有可能的切割后，函数总是返回最小值，一旦找到最小值，就将其存储起来，如果我需要再次解决这个矩形，则只需返回该值。

我想也许如果我已经解决了一个特定的矩形，现在我需要解决一个行或列更大或更小的矩形，那么我可以以某种方式使用我已经拥有的解决方案，并将其用于新的问题。但我真的不知道如何实现这样的功能。目前，我的算法将其视为全新未解决的矩形。

到目前为止，我的代码如下：

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

unsigned int M, N;
unsigned int ****pieces; ////already solved rectangles, the value of pieces[y0][x0][y1][x1] is the optimal number of pieces in which the particular rectangle(that has upperleft corner in [x0,y0] and bottomright corner in[x1,y1]) can be divided
int ****checked;
unsigned int inf;

unsigned int minbreaks(int mat[M][N], unsigned int starti, unsigned int startj, unsigned int maxi, unsigned int maxj) {
    if (pieces[starti][startj][maxi][maxj] != 0) {
        return pieces[starti][startj][maxi][maxj];
    } else {
        unsigned int vbreaks[maxj - 1];
        unsigned int hbreaks[maxi - 1];
        for (unsigned int i = 0; i < maxj - 1; i++) {
            vbreaks[i] = inf;
        }
        for (unsigned int i = 0; i < maxi - 1; i++) {
            hbreaks[i] = inf;
        }
        unsigned int currentmin = inf;

        for (unsigned int i = starti; i < maxi; i++) {
            for (unsigned int j = startj; j < maxj - 1; j++) {
                if (mat[i][j] != 2) {
                    for (unsigned int k = startj + 1; k < maxj; k++) {
                        if (vbreaks[k - 1] == inf) {
                            for (unsigned int z = starti; z < maxi; z++) {
                                if (!checked[i][j][z][k]) {
                                    if (mat[z][k] != 2 && mat[i][j] != mat[z][k]) {
                                        vbreaks[k - 1] = minbreaks(mat, starti, startj, maxi, k) + minbreaks(mat, starti, k, maxi, maxj);
                                        if (vbreaks[k - 1] < currentmin) {
                                            currentmin = vbreaks[k - 1];
                                        }
                                        break;
                                    }
                                    checked[i][j][z][k] = 1;
                                }
                            }
                        }
                    }
                }
            }
        }
        for (unsigned int i = starti; i < maxi - 1; i++) {
            for (unsigned int j = startj; j < maxj; j++) {
                if (mat[i][j] != 2) {
                    for (unsigned int k = starti + 1; k < maxi; k++) {
                        if (hbreaks[k - 1] == inf) {
                            for (unsigned int z = startj; z < maxj; z++) {
                                if (!checked[i][j][k][z]) {
                                    if (mat[k][z] != 2 && mat[i][j] != mat[k][z]) {
                                        hbreaks[k - 1] = minbreaks(mat, starti, startj, k, maxj) + minbreaks(mat, k, startj, maxi, maxj);
                                        if (hbreaks[k - 1] < currentmin) {
                                            currentmin = hbreaks[k - 1];
                                        }
                                        break;
                                    }
                                    checked[i][j][k][z] = 1;
                                }
                            }
                        }
                    }
                }
            }
        }
        if (currentmin == inf) {
            currentmin = 1;
        }
        pieces[starti][startj][maxi][maxj] = currentmin;
        return currentmin;
    }
}

int main(void) {
    FILE *file = stdin;
    fscanf(file, "%u %u", &M, &N);
    int mat[M][N];
    pieces = malloc(sizeof (unsigned int***)*M);
    checked = malloc(sizeof (int***)*M);
    for (unsigned int i = 0; i < M; i++) {//initialize the pieces,checked and mat arrays.
        pieces[i] = malloc(sizeof (unsigned int**)*N);
        checked[i] = malloc(sizeof (int**)*N);
        for (unsigned int j = 0; j < N; j++) {
            int x;
            fscanf(file, "%d", &x);
            mat[i][j] = x;
            pieces[i][j] = malloc(sizeof (unsigned int*)*(M + 1));
            checked[i][j] = malloc(sizeof (int*)*M);
            for (unsigned int y = i; y < M + 1; y++) {
                pieces[i][j][y] = malloc(sizeof (unsigned int)*(N + 1));
                for (unsigned int x = j; x < N + 1; x++) {
                    pieces[i][j][y][x] = 0;
                }
            }
            for (unsigned int y = 0; y < M; y++) {
                checked[i][j][y] = malloc(sizeof (int)*N);
                for (unsigned int x = 0; x < N; x++) {
                    checked[i][j][y][x] = 0;
                }
            }
        }
    }

    inf = M * N + 1; //number one bigger than maximal theoretically possible number of divisions
    unsigned int result = minbreaks(mat, 0, 0, M, N);
    printf("%u\n", result);
    return (EXIT_SUCCESS);
}

那么，有人有改进的想法吗？

- John Doe

---

@JohnDoe 我指的是这个交流：https://codereview.stackexchange.com/ - Christian Gibbons

@Prune 推荐 OP 在 CR 上发布帖子是可以的，但请不要将 Code Review 作为关闭问题的理由。评估请求并使用类似“过于宽泛”、“主观性太强”等原因。然后您可以提醒 OP 如果内容符合主题范围，则可以在 Code Review 上发布。请参阅 此答案中的不应该做什么部分。 - Sᴀᴍ Onᴇᴌᴀ

我们能否有这样一种情况，即在不完全分割的情况下断开部分？想象一个黑色的“L”形状，其余部分是白色的——我们是否必须分开黑色的“L”形状，还是可以仅分离白色矩形？ - גלעד ברקן

你有四层嵌套循环和一个递归调用。它们似乎没有做任何有意义的事情。你需要只有一层嵌套（即根本不嵌套）的循环，并在其中进行两个递归调用。你可以水平地将 n×m 条分成 m-1 种方式，也可以垂直地将其分成 n-1 种方式。这样就有 n-1+m-1 种方法来分割条形图。对于每个分割，你需要解决两个较小的问题。完成。 - n. m.

好的，我正在检查当前巧克力棒是否需要被打破。为什么呢？这是一个算法：solve(bar): if bar is uniform return 1; else return minimum_of (each way to make (bar = bar1 + bar2): solve(bar1) + solve(bar2))。你是如何在其中嵌套四个循环的？ - n. m.

Answer 1

对于任意矩形，我们可以在O(1)的时间内知道它是否包含白色或黑色棋子，需要分别对白色和黑色进行矩阵前缀和预处理（每个棋子计数为1）O(M * N)。

我们可以将潜在的水平和垂直分割点分别存储在两个k-d树中，以便对于任意矩形进行O(log(|splitPoints|) + k)的检索，同样需要对整个输入进行预处理。

之后，一个通用的递归算法可能如下所示：

f(tl, br):
  if storedSolution(tl, br):
    return storedSolution(tl, br)

  else if isValid(tl, br):
    return setStoredSolution(tl, br, 0)

  best = Infinity

  for p in vSplitPoints(tl, br):
    best = min(
      best,
      1 +
      f(tl, (p.x-1, br.y)) +
      f((p.x, tl.y), br)
    )

  for p in hSplitPoints(tl, br):
    best = min(
      best,
      1 +
      f(tl, (br.x, p.y-1)) +
      f((tl.x, p.y), br)
    )

  return setStoredSolution(tl, br, best)

- גלעד ברקן

Answer 2

感谢所有帮助我的人，我的错误在于那些嵌套循环中我试图避免一些不必要的breaks，比如这个例子。

1 1  -> 1 | 1
1 1     1 | 1
1 1     1 | 1

我曾尝试通过这种方式来加快运行时间，但正确的方法只是尽可能地将巧克力棒分成小块。

无论如何，对于任何感兴趣的人，这是我的可行代码：

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

unsigned int M, N;
unsigned int ****pieces; ////already solved rectangles, the value of pieces[y0][x0][y1][x1] is the optimal number of pieces in which the particular rectangle(that has upperleft corner in [x0,y0] and bottomright corner in[x1,y1]) can be divided
unsigned int inf;

int isOneColor(int mat[M][N], unsigned int starti, unsigned int startj, unsigned int maxi, unsigned int maxj) {
    int c = 2;
    for (unsigned int i = starti; i < maxi; i++) {
        for (unsigned int j = startj; j < maxj; j++) {
            if (c == 2) {
                if (mat[i][j] != 2) {
                    c = mat[i][j];
                }
            } else if (c != mat[i][j] && mat[i][j] != 2) {
                return 0;
            }
        }
    }
    return 1;
}

unsigned int minbreaks(int mat[M][N], unsigned int starti, unsigned int startj, unsigned int maxi, unsigned int maxj) {
    if (pieces[starti][startj][maxi][maxj] != 0) {
        return pieces[starti][startj][maxi][maxj];
    } else if (isOneColor(mat, starti, startj, maxi, maxj)) {
        return pieces[starti][startj][maxi][maxj] = 1;
    } else {
        unsigned int currentmin = inf;

        for (unsigned int j = startj; j < maxj - 1; j++) {
            unsigned int c = minbreaks(mat, starti, startj, maxi, j + 1) + minbreaks(mat, starti, j + 1, maxi, maxj);
            if (c < currentmin) {
                currentmin = c;
            }
        }
        for (unsigned int i = starti; i < maxi - 1; i++) {
            unsigned int c = minbreaks(mat, starti, startj, i + 1, maxj) + minbreaks(mat, i + 1, startj, maxi, maxj);
            if (c < currentmin) {
                currentmin = c;
            }
        }

        pieces[starti][startj][maxi][maxj] = currentmin;
        return currentmin;
    }
}

int main(void) {
    FILE *file = stdin;
    //FILE *file = fopen("inputfile", "r");
    fscanf(file, "%u %u", &M, &N);
    int mat[M][N];
    pieces = malloc(sizeof (unsigned int***)*M);
    for (unsigned int i = 0; i < M; i++) {
        pieces[i] = malloc(sizeof (unsigned int**)*N);
        for (unsigned int j = 0; j < N; j++) {
            int x;
            fscanf(file, "%d", &x);
            mat[i][j] = x;
            pieces[i][j] = malloc(sizeof (unsigned int*)*(M + 1));
            for (unsigned int y = i; y < M + 1; y++) {
                pieces[i][j][y] = malloc(sizeof (unsigned int)*(N + 1));
                for (unsigned int x = j; x < N + 1; x++) {
                    pieces[i][j][y][x] = 0;
                }
            }
        }
    }

    inf = M * N + 1; //number that is bigger by one than maximal theoretically possible number of divisions
    unsigned int result = minbreaks(mat, 0, 0, M, N);
    printf("%u\n", result);
    return (EXIT_SUCCESS);
}

- John Doe

Answer 3

有一种动态规划方法可以解决这个问题，但它也不便宜。您需要填写大量表格，为主正方形内每个矩形的大小和位置提供最小分割次数。

对于1x1大小的矩形，答案是0。

对于大小为AxB的矩形，请查看并确定其所有单元格是否足够均匀，使该矩形的答案为0。如果是，则很好。如果不是，请尝试所有可能的水平和垂直分割。每个分割都会给您两个较小的矩形。如果在尝试计算大小为A-1xB及更小和大小为AxB-1及更小的所有矩形的答案之前，您计算了所有较小矩形的答案，则您已经知道了两个较小矩形的答案。因此，对于每个可能的分割，将两个较小矩形的答案相加并加上1以获取该分割的成本。选择给出最小成本的分割即可得到当前AxB矩形的答案。

在计算较大矩形之前计算所有较小矩形的答案，最后一个答案即为完整正方形的最佳分割次数。计算最佳分割的最简单方法是为每个矩形保留一些额外信息，记录找到的最佳分割。

对于一个NxN的正方形，有O(N^4)个矩形 - 正方形中的任意两点都可以定义一个以它们为对角线的矩形。一个大小为O(N)xO(N)的矩形有O(N)种可能的分割，因此你需要像O(N^5)算法那样的东西，或者如果N是输入大小，那么就是O(N^2.5)，因为一个NxN的正方形具有O(N^2)的输入数据大小。

（您也可以通过使用minBreaks()函数的调用结果来存储原始代码的结果，以便如果使用相同的参数多次调用minBreaks()函数，则它将简单地返回存储的答案，而不是通过更多的递归调用重新计算。）

- mcdowella

---

实际上，我的minBreaks()函数已经完成了这个任务，我将解决的矩形存储在int ****pieces数组中。 - John Doe

它的价格足够便宜。40x40的示例在合理的桌面上需要约0.1秒，对于随机的50x50条形图需要约0.5秒。 - n. m.

@n.m. 你能否请发一下你的解决方案？对我来说，在40x40的情况下，它肯定不会在0.1秒内完成。 - John Doe

@JohnDoe 对不起，我不会在其他人的家庭作业任务中发布完整的解决方案。 - n. m.