leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

2257.cpp (1104B)

      1 class Solution {
      2   public:
      3     int countUnguarded(const int n, const int m, const vector<vector<int>> &guards,
      4                        const vector<vector<int>> &walls) const {
      5         const auto idx = [m](int x, int y) { return x * m + y; };
      6 
      7         bitset<100001> stop = 0, seen = 0;
      8         for (const auto &wall : walls)
      9             stop.set(idx(wall[0], wall[1]));
     10         for (const auto &guard : guards)
     11             stop.set(idx(guard[0], guard[1]));
     12 
     13         static const int offset[] = {-1, 0, 1, 0, -1};
     14 
     15         int res = m * n - size(walls) - size(guards);
     16         for (const auto &guard : guards) {
     17             for (int k = 0; k < 4; k++) {
     18                 int x = guard[0] + offset[k], y = guard[1] + offset[k + 1];
     19                 while (x >= 0 && x < n && y >= 0 && y < m) {
     20                     const int index = idx(x, y);
     21                     if (stop.test(index)) break;
     22                     if (!seen.test(index)) res--;
     23                     seen.set(index);
     24                     x += offset[k], y += offset[k + 1];
     25                 }
     26             }
     27         }
     28 
     29         return res;
     30     }
     31 };