aboutsummaryrefslogtreecommitdiff
path: root/find_min_area_conver_ones2.c
blob: 363210e2a69375ed38c36830a3e6a7eacbdd2d7d (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
// 3197. Find the Minimum Area to Cover All Ones II
#include "leetcode.h"

/*
 * you are giiven a 2d binary array 'grid'. you need to find 3 non-overlapping
 * rectangles having non-zero areas with horizontal and vertical sides such that
 * all the 1's in the 'grid' lie inside these rectangles. return the minimum
 * possible sum of the area of these rectangles. note that the rectangles are
 * allowed to touch.
 */

int min_area(int **grid, int gridSize, int gridColSize) {
  int left = 1e9, top = 1e9, right = -1, bottom = -1;
  for (int i = 0; i < gridSize; i++) {
    for (int j = 0; j < gridColSize; j++) {
      if (grid[i][j] == 1) {
        if (j < left)
          left = j;
        if (i < top)
          top = i;
        if (j > right)
          right = j;
        if (i > bottom)
          bottom = i;
      }
    }
  }
  if (right == -1)
    return 0;
  return (right - left + 1) * (bottom - top + 1);
}

int **rotate(int **grid, int gridSize, int gridColSize) {
  int **res = (int **)malloc(gridColSize * sizeof(int *));
  for (int i = 0; i < gridColSize; i++)
    res[i] = (int *)malloc(gridSize * sizeof(int));
  for (int i = 0; i < gridSize; i++)
    for (int j = 0; j < gridColSize; j++)
      res[j][gridSize - 1 - i] = grid[i][j];
  return res;
}

int minimumSum(int **grid, int gridSize, int *gridColSize) {
  int ans = 1e9;
  for (int rot = 0; rot < 4; rot++) {
    int m = gridColSize[0];
    for (int i = 1; i < gridSize; i++) {
      int a1 = min_area(grid, i, m);
      for (int j = 1; j < m; j++) {
        int **p2 = (int **)malloc((gridSize - i) * sizeof(int *));
        int **p3 = (int **)malloc((gridSize - i) * sizeof(int *));
        for (int r = 0; r < gridSize - i; r++) {
          p2[r] = (int *)malloc(j * sizeof(int));
          p3[r] = (int *)malloc((m - j) * sizeof(int));
          for (int c = 0; c < j; c++)
            p2[r][c] = grid[i + r][c];
          for (int c = j; c < m; c++)
            p3[r][c - j] = grid[i + r][c];
        }
        int a2 = min_area(p3, gridSize - i, j);
        int a3 = min_area(p3, gridSize - i, m - j);
        if (a1 + a2 + a3 < ans)
          ans = a1 + a2 + a3;
      }
    }
    grid = rotate(grid, gridSize, gridColSize[0]);
    int tmp = gridSize;
    gridSize = gridColSize[0];
    gridColSize[0] = tmp;
  }
  return ans;
}

int main() {
  int g1i[2][3] = {{1, 0, 1}, {1, 1, 1}},
      g2i[2][4] = {{1, 0, 1, 0}, {0, 1, 0, 1}};
  struct two_d_arr *g1 =
      two_d_arr_init(ARRAY_SIZE(g1i), ARRAY_SIZE(g1i[0]), g1i);
  struct two_d_arr *g2 =
      two_d_arr_init(ARRAY_SIZE(g2i), ARRAY_SIZE(g2i[0]), g2i);
  printf("%d\n", minimumSum(g1->arr, g1->row_size, g1->col_size)); // expect: 5
  printf("%d\n", minimumSum(g2->arr, g2->row_size, g2->col_size)); // expect: 5
  two_d_arr_free(g1);
  two_d_arr_free(g2);
}