leetcode

commit 9ed9c25cd8954b88019c6d7dfd92996cf1889f5f
parent 7bf19b0fc7433773da4f2992fe4591a781a63b4a
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Fri, 13 Dec 2024 14:19:56 +0100

1 Random Problem

Diffstat:
A
Problems/1284.cpp
 | 
39
+++++++++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 40 insertions(+), 0 deletions(-)
diff --git a/Problems/1284.cpp b/Problems/1284.cpp
@@ -0,0 +1,39 @@
+class Solution {
+  public:
+    int minFlips(const vector<vector<int>> &mat) const {
+        static const int offset[] = {-1, 0, 1, 0, -1};
+        const int n = size(mat), m = size(mat[0]);
+        unsigned res = -1;
+
+        const auto valid = [&](int x, int y) { return x >= 0 && x < n && y >= 0 && y < m; };
+
+        for (unsigned mask = 0; mask < 1 << (n * m); mask++) {
+            auto grid = mat;
+
+            for (unsigned k = 0, crnt = mask; crnt; crnt >>= 1, k++) {
+                if (!(crnt & 1)) continue;
+
+                const int a = k / m, b = k % m;
+                for (int k = 0; k < 4; k++) {
+                    const int x = a + offset[k + 1];
+                    const int y = b + offset[k];
+
+                    if (!valid(x, y)) continue;
+                    grid[x][y] = !grid[x][y];
+                }
+                grid[a][b] = !grid[a][b];
+            }
+
+            for (int i = 0; i < n; i++) {
+                for (int j = 0; j < m; j++) {
+                    if (grid[i][j]) goto next;
+                }
+            }
+
+            res = min(res, (unsigned)popcount(mask));
+        next:;
+        }
+
+        return res;
+    }
+};
diff --git a/README.md b/README.md
@@ -834,6 +834,7 @@ reference and a base for solving problems.
 |  1280  |    Easy    | [Students and Examinations](Problems/1280.cpp)                                                     |
 |  1282  |   Medium   | [Group the People Given the Group Size They Belong To](Problems/1282.cpp)                          |
 |  1283  |   Medium   | [Find the Smallest Divisor Given a Threshold](Problems/1283.cpp)                                   |
+|  1284  |    Hard    | [Minimum Number of Flips to Convert Binary Matrix to Zero Matrix](Problems/1284.cpp)               |
 |  1286  |   Medium   | [Iterator for Combination](Problems/1286.cpp)                                                      |
 |  1287  |    Easy    | [Element Appearing More Than 25% In Sorted Array](Problems/1287.cpp)                               |
 |  1288  |   Medium   | [Remove Covered Intervals](Problems/1288.cpp)                                                      |