aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-12-20 01:21:14 -0700
committerJack Sangdahl <[email protected]>2024-12-20 01:21:14 -0700
commit4d70be0e550fcc570dbde58c4001e074e7cf357a (patch)
tree789678eadcb57aaa7f12964373ea74bb40367716
parent2199755f6718c0f5489248efa46768ca0da7b430 (diff)
downloadleetcode-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.c85
-rw-r--r--max_num_flips_binary_matrix.py42
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]]))