aboutsummaryrefslogtreecommitdiff
path: root/min_operations_write_y_grid.c
blob: 96f082e0f1389e9804a5f7cdb953a32e5517f014 (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
// 3071. Minimum Operations to Write the Letter Y on a Grid
#include "leetcode.h"

/*
 * you are given a 0-indexed 'n x n' grid where 'n' is odd, and 'grid[r][c]' is
 * 0, 1, or 2. we say that a cell belongs to the letter y if it belongs to one
 * of the following: the diagonal starting at the top-left cell and ending at
 * the center cell of the grid, the diagonal starting at the top-right cell nd
 * ending at the center cell of the grid, or the vertical line starting at the
 * center cell and ending at the bottom border of the grid. return the minimum
 * number of operations needed to write the letter y on the grid given that in
 * one operation you can change the value at cell to 0, 1, or 2.
 */

int minimumOperationsToWriteY(int **grid, int gridSize, int *gridColSize) {
  int hash_y[4], hash_all[4];
  memset(hash_y, 0, sizeof(hash_y));
  memset(hash_all, 0, sizeof(hash_all));
  int half_length = gridSize / 2;
  for (int i = 0; i < gridSize; i++)
    for (int j = 0; j < *gridColSize; j++)
      hash_all[grid[i][j]]++;
  hash_all[3] = gridSize * (*gridColSize);
  hash_y[grid[half_length][half_length]]++;
  hash_y[3]++;
  for (int i = 0; i < half_length; i++) {
    hash_y[grid[i][i]]++;
    hash_y[grid[i][gridSize - i - 1]]++;
    hash_y[grid[half_length + i + 1][half_length]]++;
    hash_y[3] += 3;
  }
  for (int i = 0; i < 4; i++)
    hash_all[i] -= hash_y[i];
  int min_ops = INT_MAX, curr_ops;
  for (int i = 0; i < 3; i++) {
    curr_ops = hash_y[3] - hash_y[i] + hash_all[i];
    for (int j = 0; j < 3; j++)
      if (i != j)
        min_ops = fmin(min_ops, curr_ops);
  }
  return min_ops;
}

int main() {
  int g1i[3][3] = {{1, 2, 2}, {1, 1, 0}, {0, 1, 0}};
  int g2i[5][5] = {{0, 1, 0, 1, 0},
                   {2, 1, 0, 1, 2},
                   {2, 2, 2, 0, 1},
                   {2, 2, 2, 2, 2},
                   {2, 1, 2, 2, 2}};
  struct two_d_arr g1, g2;
  two_d_arr_init(&g1, 3, 3, g1i);
  two_d_arr_init(&g2, 5, 2, g2i);
  printf("%d\n", minimumOperationsToWriteY(g1.arr, g1.row_size,
                                           g1.col_size)); // expect: 3
  printf("%d\n", minimumOperationsToWriteY(g2.arr, g2.row_size,
                                           g2.col_size)); // expect: 12
  two_d_arr_free(&g1);
  two_d_arr_free(&g2);
}