diff options
author | Jack Sangdahl <[email protected]> | 2024-12-20 01:21:14 -0700 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-12-20 01:21:14 -0700 |
commit | 4d70be0e550fcc570dbde58c4001e074e7cf357a (patch) | |
tree | 789678eadcb57aaa7f12964373ea74bb40367716 | |
parent | 2199755f6718c0f5489248efa46768ca0da7b430 (diff) | |
download | leetcode-4d70be0e550fcc570dbde58c4001e074e7cf357a.tar.gz leetcode-4d70be0e550fcc570dbde58c4001e074e7cf357a.zip |
1284. minimum number of flips to convert binary matrix to zero matrix
-rw-r--r-- | max_num_flips_binary_matrix.c | 85 | ||||
-rw-r--r-- | max_num_flips_binary_matrix.py | 42 |
2 files changed, 127 insertions, 0 deletions
diff --git a/max_num_flips_binary_matrix.c b/max_num_flips_binary_matrix.c new file mode 100644 index 0000000..a5a5565 --- /dev/null +++ b/max_num_flips_binary_matrix.c @@ -0,0 +1,85 @@ +// 1284. Minimum Number of Flips to Convert Binary Matrix to Zero Matrix +#include "leetcode.h" + +/* + * given an 'm x n' binary matrix 'mat'. in one step, you can choose one cell + * and flip it and all the four neighbours of it if they exist (fip is changing + * 1 to 0, and 0 to 1). a pair ofcells are called neighbours if their share one + * edge. return the minimum number of steps required to convert 'mat' to a zero + * matrix or -1 if you cannot. a binary matrix isa matrix with all cells equal + * to 0 or 1 only. a zero matrix is a matrix with all cells equal to 0. + */ + +struct queue_node { + int state; + int step; +}; + +void push(struct queue_node q[], int *tail, int state, int step) { + q[*tail].state = state; + q[*tail].step = step; + (*tail)++; +} + +int pop_state(struct queue_node q[], int *head) { + (*head)++; + return q[*head].state; +} + +int pop_step(struct queue_node q[], int *head) { return q[*head].step; } + +int minFlips(int **mat, int matSize, int *matColSize) { + int n = matSize, m = *matColSize, start = 0, head = -1, tail = 0; + int dx[5] = {0, 0, 1, 0, -1}; + int dy[5] = {0, 1, 0, -1, 0}; + struct queue_node *q = + (struct queue_node *)malloc((1 << (n * m)) * sizeof(struct queue_node)); + for (int i = 0; i < n; i++) + for (int j = 0; j < m; j++) + if (mat[i][j]) + start += 1 << (j + i * m); + if (!start) + return 0; + bool *occur = (bool *)calloc(1, (1LL << (n * m)) * sizeof(bool)); + occur[start] = true; + push(q, &tail, start, 0); + while (head + 1 < tail) { + int curr_state = pop_state(q, &head); + int curr_step = pop_step(q, &head); + for (int i = 0; i < n; i++) { + for (int j = 0; j < m; j++) { + int new_state = curr_state; + for (int k = 0; k < 5; k++) { + int nx = i + dx[k]; + int ny = j + dy[k]; + if (nx >= 0 && nx < n && ny >= 0 && ny < m) + new_state ^= 1 << (ny + nx * m); + } + if (!new_state) { + free(q), free(occur); + return curr_step + 1; + } else if (!occur[new_state]) { + occur[new_state] = true; + push(q, &tail, new_state, curr_step + 1); + } + } + } + } + free(q), free(occur); + return -1; +} + +int main() { + int m1i[2][2] = {{0, 0}, {0, 1}}, m2i[1][1] = {{0}}, + m3i[2][3] = {{1, 0, 0}, {1, 0, 0}}; + struct two_d_arr m1, m2, m3; + two_d_arr_init(&m1, 2, 2, m1i); + two_d_arr_init(&m2, 1, 1, m2i); + two_d_arr_init(&m3, 2, 3, m3i); + printf("%d\n", minFlips(m1.arr, m1.row_size, m1.col_size)); // expect: 3 + printf("%d\n", minFlips(m2.arr, m2.row_size, m2.col_size)); // expect: 0 + printf("%d\n", minFlips(m3.arr, m3.row_size, m3.col_size)); // expect: -1 + two_d_arr_free(&m1); + two_d_arr_free(&m2); + two_d_arr_free(&m3); +} diff --git a/max_num_flips_binary_matrix.py b/max_num_flips_binary_matrix.py new file mode 100644 index 0000000..a29caa0 --- /dev/null +++ b/max_num_flips_binary_matrix.py @@ -0,0 +1,42 @@ +# 1284. Minimum Number of Flips to Convert Binary Matrix to Zero Matrix + +""" +given an 'm x n' binary matrix 'mat'. in one step, you can choose one cell +and flip it and all the four neighbours of it if they exist (fip is changing +1 to 0, and 0 to 1). a pair ofcells are called neighbours if their share one +edge. return the minimum number of steps required to convert 'mat' to a zero +matrix or -1 if you cannot. a binary matrix isa matrix with all cells equal +to 0 or 1 only. a zero matrix is a matrix with all cells equal to 0. +""" + + +class Solution(object): + def minFlips(self, mat): + """ + :type mat: List[List[int]] + :rtype: int + """ + m, n = len(mat), len(mat[0]) + start = sum( + cell << i * n + j for i, row in enumerate(mat) for j, cell in enumerate(row) + ) + stack, seen = [(start, 0)], {start: 0} + while stack: + curr, step = stack.pop() + for i in range(m): + for j in range(n): + next = curr + for r, c in (i, j), (i, j + 1), (i, j - 1), (i + 1, j), (i - 1, j): + if m > r >= 0 <= c < n: + next ^= 1 << r * n + c + if seen.get(next, float("inf")) > step + 1: + seen[next] = step + 1 + stack.append((next, step + 1)) + return seen.get(0, -1) + + +if __name__ == "__main__": + obj = Solution() + print(obj.minFlips(mat=[[0, 0], [0, 1]])) + print(obj.minFlips(mat=[[0]])) + print(obj.minFlips(mat=[[1, 0, 0], [1, 0, 0]])) |