Finding a minimal set of rectangles covering a binary matrix [duplicate]

Question

Say I have the following binary matrix:

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

I want to find the set of rectangles parallel to the x and y axis that covers every 1 at least once and covers not a single 0 which has minimal cardinality (the least amount of rectangles). In the example above this would be the rectangles ((0, 3), (6, 5)) and ((3, 0), (5, 8)) (notation is in the form (topleft, bottomright)) - the minimal solution is using two rectangles.

My previous attempt was finding the rectangle with the largest area covering only 1's, adding that rectangle to the set and then marking all those 1's as 0's, until all 1's are gone. While this set would cover every 1 and not a single 0, it won't necessarily have minimal cardinality (this algorithm will fail on the example above).

Answer 1

I think you should replace covered 1's with 2's instead of 0's. This way you can include the 2's when covering 1's and still not cover any 0's.

Here's what I came up with:

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

Example input 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

Example input 2:

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