寻找覆盖二进制矩阵的最小矩形集合

Question

假设我有以下二进制矩阵：

0 0 0 1 1 1 0
0 0 0 1 1 1 0
0 0 0 1 1 1 0
1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1
0 0 0 1 1 1 0
0 0 0 1 1 1 0
0 0 0 1 1 1 0

我想找到与x和y轴平行的矩形集，至少覆盖每个1一次，并且不覆盖任何单个0，其基数最小（矩形数量最少）。 在上面的示例中，这将是矩形((0,3),(6,5))和((3,0),(5,8))(表示为(topleft,bottomright)）。最小解决方案使用两个矩形。

我之前的尝试是找到覆盖只有1的最大区域的矩形，将该矩形添加到集合中，然后将所有1标记为0，直到所有1都消失。虽然此集合将覆盖每个1并且不覆盖任何单个0，但它不一定具有最小的基数（此算法将在上述示例中失败）。

- orlp

---

最小解是指最少的矩形数量还是最少的最小矩形数量？或者是最少数量的矩形，这些矩形共同拥有最少数量的“1”？ - YePhIcK

@YePhIcK：最小矩形集意味着无论大小，都是最少的矩形。 - Wug

一个单独的1可以是两个矩形的一部分吗？还是这些矩形必须是不相交的？ - Aman Deep Gautam

@AmanDeepGautam：每个1都必须是__至少__一个矩形的一部分，所以两个、三个等等都可以。 - orlp

为什么要关闭这个问题？它是一个五年前的问题，甚至不是你关闭的答案的实际重复。我的问题允许重叠。 - orlp

Answer 1

我认为你应该用2替换已覆盖的1，而不是0。这样，当覆盖1时，您可以包括2，但仍然不会覆盖任何0。

这是我想到的:

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

struct board {
  int **data;
  int w,h;
};

int  load_board(char *, struct board *);
void print_board(struct board *);

int  max_height_with_fixed_w(struct board *board, int i, int j, int w) {
  int jj = -1, ii;
  if (board->data[j][i] != 0) {
    for (jj = j; jj < board->h && board->data[jj][i] != 0; jj++) { 
      for (ii = i; ii - i < w; ii++) {
        if (board->data[jj][ii] == 0)
          return jj - j;
      }
    }
    printf("maximum height = %d\n", jj);
  }
  return jj - j;
}

void find_largest_rect_from(
    struct board *board, 
    int i, int j, int *ei, int *ej) {
  int max_w = 0, max_h = 0, max_a = 0;
  *ei = *ej = -1;
  for (max_w = 0; max_w < board->w - i && 
      (board->data[j][i + max_w] != 0); 
      max_w++) {
    int max_aa;
    int max_hh = max_height_with_fixed_w(board, i, j, max_w + 1);
    if (max_hh > max_h) {
      max_h  = max_hh; 
    }
    max_aa = max_hh * (max_w + 1);
    printf("  area: %d x %d = %d\n", max_hh, max_w + 1, max_aa);
    if (max_aa > max_a) {
      max_a = max_aa;
      *ei = i + max_w;
      *ej = j + max_hh - 1; 
    }
  }
  printf("max width : %d\n", max_w);
  printf("max height: %d\n", max_h);
  printf("max area  : %d\n", max_a);
}

int main(int arc, char **argv) {
  struct board board;
  int jj, ii, i = 0, j = 0;
  int total_rects = 0;
  if(load_board(argv[1], &board)) return 1;
  print_board(&board);
  for (j = 0; j < board.h; j++) {
    for (i = 0; i < board.w; i++) {
      if (board.data[j][i] == 1) {
        find_largest_rect_from(&board, i, j, &ii, &jj);
        printf("largest from %d, %d ends at %d,%d\n", i, j, ii, jj);
        int marki, markj;
        total_rects++;
        for (markj = j; markj <= jj; markj++) {
          for (marki = i; marki <= ii; marki++) {
            board.data[markj][marki] = 2;
          }
        }
        print_board(&board);
      }
    }
  }
  printf("minimum %d rects are required\n", total_rects);
  return 0;
}

int load_board(char *fname, struct board *board) {
  FILE *file = fopen(fname, "r");
  int j,i;
  if (!file) return 1;
  fscanf(file, "%d %d", &board->w, &board->h);
  board->data = (int**)malloc(sizeof(int*)*board->h);
  for (j = 0; j < board->h; j++) {
    board->data[j] = (int*)malloc(sizeof(int)*board->w);
    for (i = 0; i < board->w; i++) {
      fscanf(file, "%d", &board->data[j][i]);
    }
  }
  return 0;
}

void print_board(struct board *board) {
  int i,j;
  printf("board size: %d, %d\n", board->w, board->h);
  for (j = 0; j < board->h; j++) {
    for (i = 0; i < board->w; i++) {
      printf("%d ", board->data[j][i]);
    } printf("\n");
  }
}

示例输入1：

7 9
0 0 0 1 1 1 0
0 0 0 1 1 1 0
0 0 0 1 1 1 0
1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1
0 0 0 1 1 1 0
0 0 0 1 1 1 0
0 0 0 1 1 1 0

第二个示例输入：

7 7
0 0 0 1 0 0 0
0 0 1 1 1 0 0
0 1 1 1 1 1 0
1 1 1 1 1 1 1
0 1 1 1 1 1 0
0 0 1 1 1 0 0
0 0 0 1 0 0 0

- perreal

---

我正想着那件事呢！ - YePhIcK

好的观点，但那只是技术上的细节，而不是算法层面的。 - Nir Alfasi

@alfasin：我相信他可以使用现有的算法进行修改。 - Wug

我认为这会起作用。我正在使用这个算法：https://dev59.com/TGs05IYBdhLWcg3wSP9H#7497967 如果我简单地跳过2，我认为我会找到最大的剩余矩形。 - orlp

Answer 2

一个算法的想法：

• 只要矩阵中有1，就执行以下操作：
• 对于每个没有上方和左侧都有1的1，执行以下操作：
• 贪心策略：从这个1开始，向右下方对角线走，只要路上有1，就创建一个矩形，并将所创建矩形内的1改为0。

- Nir Alfasi

Answer 3

我会选择一个选点并扩展的算法，直到消耗所有可能的空间，然后再选择更多，直到网格上的所有点都被消耗。

以您的示例为例，假设我们正在消耗1s。

我会选择(0,3)，最左边的最上面的1。我的矩形将从大小为0,0开始。我会向右和向下扩展，直到它增长到6,2的大小。此时，我会将这些点标记为已占用。

然后我会选择另一个点，比如(3,0)，矩形大小为0,0。我会向下和向右扩展，直到它占据了最大的可用空间，大小为2,6。

考虑以下内容：

0 0 0 1 0 0 0
0 0 1 1 1 0 0
0 1 1 1 1 1 0
1 1 1 1 1 1 1
0 1 1 1 1 1 0
0 0 1 1 1 0 0
0 0 0 1 0 0 0

你可以轻松地确定对于任何随机起点，它总是需要4个矩形。

为了将点标记为“已占用”，您应该将它们与标记为“不可消耗”的点区别开来。然后，您可以区分不可扩展的点（无法扩展）和“已占用”的点（可以扩展，但不必扩展，因为它们已经被占用）。

- Wug