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

Question

我的学校作业有问题。我有一 block 巧克力，由黑色、白色或黑白(混合)方 block 组成。我应该把它分成两组，一组只有白色或黑白片，另一组只有黑色或黑白片。分割巧克力棒意味着沿着分隔各个方 block 的线将其水平或垂直打碎。

给定巧克力 block 的布局，我要找到一个最佳划分，将黑色和白色立方体分开，并得到尽可能少的 block 数，巧克力 block 不大于 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);
}

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

Answer 1

对于任意矩形，我们可以知道它在 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)