カバーされた 1 を 0 ではなく 2 に置き換える必要があると思います。このようにして、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
入力例 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