使用规则在矩形巧克力棒中找到最小数量的矩形块

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 个新出现的矩形做同样的事情，如果它们不能再被分割，那么 return 1.

函数在遍历所有可能的切割后总是returns 最小值，一旦找到最小值然后存储它，如果我碰巧需要再次解决这个矩形那么只需return值。

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

到目前为止我的代码：

#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);
}

所以有人有改进的想法吗？

Answer 1

对此有一种动态规划方法，但它也不会便宜。您需要填写大量表格，针对主广场内矩形的每个大小和位置，给出完全划分较小矩形所需的最小分割数。

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

对于大小为 AxB 的矩形，查看其所有单元格是否足够均匀，以至于该矩形的答案为 0。如果是这样，很好。如果不尝试所有可能的水平和垂直划分。这些分区中的每一个都会为您提供两个较小的矩形。如果您在尝试计算大小为 AxB 的矩形的答案之前计算出所有大小为 A-1xB 和更小的矩形以及大小为 AxB-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() 它只是 returns 存储的答案，而不是通过对 minBreaks() 的更多递归调用来重新计算它。

Answer 2

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

我们可以将潜在的水平和垂直分割点分别存储在两个 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 3

感谢所有帮助过我的人，我的错误是在那些嵌套循环中我试图避免一些不必要的中断，例如这样

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);
}