leetcode

commit 474a0b7635ce3991eb3ff06b2a99a0b940afa87b
parent a036c2e1f7609b9e25609f60c5bd419ee69f9ff8
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Tue, 26 Mar 2024 18:23:19 +0000

1 Random Problem

Diffstat:
A
Problems/2257.cpp
 | 
31
+++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 32 insertions(+), 0 deletions(-)
diff --git a/Problems/2257.cpp b/Problems/2257.cpp
@@ -0,0 +1,31 @@
+class Solution {
+  public:
+    int countUnguarded(const int n, const int m, const vector<vector<int>> &guards,
+                       const vector<vector<int>> &walls) const {
+        const auto idx = [m](int x, int y) { return x * m + y; };
+
+        bitset<100001> stop = 0, seen = 0;
+        for (const auto &wall : walls)
+            stop.set(idx(wall[0], wall[1]));
+        for (const auto &guard : guards)
+            stop.set(idx(guard[0], guard[1]));
+
+        static const int offset[] = {-1, 0, 1, 0, -1};
+
+        int res = m * n - size(walls) - size(guards);
+        for (const auto &guard : guards) {
+            for (int k = 0; k < 4; k++) {
+                int x = guard[0] + offset[k], y = guard[1] + offset[k + 1];
+                while (x >= 0 && x < n && y >= 0 && y < m) {
+                    const int index = idx(x, y);
+                    if (stop.test(index)) break;
+                    if (!seen.test(index)) res--;
+                    seen.set(index);
+                    x += offset[k], y += offset[k + 1];
+                }
+            }
+        }
+
+        return res;
+    }
+};
diff --git a/README.md b/README.md
@@ -1030,6 +1030,7 @@ for solving problems.
 |  2244  |   Medium   | [Minimum Rounds to Complete All Tasks](Problems/2244.cpp)                                          |
 |  2246  |    Hard    | [Longest Path With Different Adjacent Characters](Problems/2246.cpp)                               |
 |  2251  |    Hard    | [Number of Flowers in Full Bloom](Problems/2251.cpp)                                               |
+|  2257  |   Medium   | [Count Unguarded Cells in the Grid](Problems/2257.cpp)                                             |
 |  2264  |    Easy    | [Largest 3-Same-Digit Number in String](Problems/2264.cpp)                                         |
 |  2265  |   Medium   | [Count Nodes Equal to Average of Subtree](Problems/2265.cpp)                                       |
 |  2265  |   Medium   | [Count Nodes Equal to Average of Subtree](Problems/2265.cpp)                                       |