diff options
author | Jack Sangdahl <[email protected]> | 2025-04-15 20:04:10 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-04-15 20:04:10 -0600 |
commit | 87c40729389ab33c8ad1a86faf6f45e9d8b20fe4 (patch) | |
tree | 4209d18287daec663de3b01bfcf95ac76b1e0fd4 | |
parent | e7bc454ca4a66df33ad0db3c69ff3f68b529f008 (diff) | |
download | leetcode-87c40729389ab33c8ad1a86faf6f45e9d8b20fe4.tar.gz leetcode-87c40729389ab33c8ad1a86faf6f45e9d8b20fe4.zip |
3240. minimum number of flips to make binary grid palindromic 2
-rw-r--r-- | min_num_flip_bin_grid_palin2.c | 50 | ||||
-rw-r--r-- | min_num_flip_bin_grid_palin2.py | 42 |
2 files changed, 92 insertions, 0 deletions
diff --git a/min_num_flip_bin_grid_palin2.c b/min_num_flip_bin_grid_palin2.c new file mode 100644 index 0000000..fe3ffdf --- /dev/null +++ b/min_num_flip_bin_grid_palin2.c @@ -0,0 +1,50 @@ +// 3240. Minimum Number of Flips to Make Binary Grid Palindromic II +#include "leetcode.h" + +/* + * you are given an 'm x n' binary matrix 'grid'. a row or column is considered + * palindromic if its values read the same forward as backward. you can flip any + * number of cells in 'grid' from 0 to 1 or from 1 to 0. return the minimum + * number of cells that need to be flipped to make all rows and columns + * palindromic and the total number of 1s in 'grid' divisible by 4. + */ + +int minFlips(int **grid, int gridSize, int *gridColSize) { + int ans = 0, one = 0, diff = 0, m = gridSize, n = gridColSize[0]; + for (int i = 0; i < m / 2; ++i) + for (int j = 0; j < n / 2; ++j) { + int v = grid[i][j] + grid[i][n - 1 - j] + grid[m - 1 - i][j] + + grid[m - 1 - i][n - 1 - j]; + ans += fmin(v, 4 - v); + } + if (n % 2) + for (int i = 0; i < m / 2; ++i) { + diff += grid[i][n / 2] != grid[m - 1 - i][n / 2]; + one += grid[i][n / 2] + grid[m - 1 - i][n / 2]; + } + if (m % 2) + for (int j = 0; j < n / 2; ++j) { + diff += grid[m / 2][j] != grid[m / 2][n - 1 - j]; + one += grid[m / 2][j] + grid[m / 2][n - 1 - j]; + } + if (n % 2 && m % 2) + ans += grid[m / 2][n / 2]; + if (!diff && one % 4) + ans += 2; + return ans + diff; +} + +int main() { + int g1i[3][3] = {{1, 0, 0}, {0, 1, 0}, {0, 0, 1}}, + g2i[3][2] = {{0, 1}, {0, 1}, {0, 0}}, g3i[2][1] = {{1}, {1}}; + struct two_d_arr g1, g2, g3; + two_d_arr_init(&g1, ARRAY_SIZE(g1i), ARRAY_SIZE(g1i[0]), g1i); + two_d_arr_init(&g2, ARRAY_SIZE(g2i), ARRAY_SIZE(g2i[0]), g2i); + two_d_arr_init(&g3, ARRAY_SIZE(g3i), ARRAY_SIZE(g3i[0]), g3i); + printf("%d\n", minFlips(g1.arr, g1.row_size, g1.col_size)); // expect: 3 + printf("%d\n", minFlips(g2.arr, g2.row_size, g2.col_size)); // expect: 2 + printf("%d\n", minFlips(g3.arr, g3.row_size, g3.col_size)); // expect: 2 + two_d_arr_free(&g1); + two_d_arr_free(&g2); + two_d_arr_free(&g3); +} diff --git a/min_num_flip_bin_grid_palin2.py b/min_num_flip_bin_grid_palin2.py new file mode 100644 index 0000000..3f196bb --- /dev/null +++ b/min_num_flip_bin_grid_palin2.py @@ -0,0 +1,42 @@ +# 3240. Minimum Number of Flips to Make Binary Grid Palindromic II + +""" +you are given an 'm x n' binary matrix 'grid'. a row or column is considered +palindromic if its values read the same forward as backward. you can flip any +number of cells in 'grid' from 0 to 1 or from 1 to 0. return the minimum +number of cells that need to be flipped to make all rows and columns +palindromic and the total number of 1s in 'grid' divisible by 4. +""" + + +class Solution(object): + def minFlips(self, grid): + """ + :type grid: List[List[int]] + :rtype: int + """ + ans, one, diff, m, n = 0, 0, 0, len(grid), len(grid[0]) + for i in range(m // 2): + for j in range(n // 2): + v = grid[i][j] + grid[i][~j] + grid[~i][j] + grid[~i][~j] + ans += min(v, 4 - v) + if n % 2: + for i in range(m // 2): + diff += grid[i][n // 2] ^ grid[~i][n // 2] + one += grid[i][n // 2] + grid[~i][n // 2] + if m % 2: + for i in range(n // 2): + diff += grid[m // 2][j] ^ grid[m // 2][~j] + one += grid[m // 2][j] + grid[m // 2][~j] + if n % 2 and m % 2: + ans += grid[m // 2][n // 2] + if diff == 0 and one % 4: + ans += 2 + return ans + diff + + +if __name__ == "__main__": + obj = Solution() + print(obj.minFlips(grid=[[1, 0, 0], [0, 1, 0], [0, 0, 1]])) + print(obj.minFlips(grid=[[0, 1], [0, 1], [0, 0]])) + print(obj.minFlips(grid=[[1], [1]])) |