leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

2201.cpp (1086B)

0 class Solution { 1 public: 2 int digArtifacts(int n, const vector<vector<int>> &artifacts, const vector<vector<int>> &dig) const { 3 vector<vector<int>> grid(n, vector(n, 0)); 4 for (const auto &d : dig) 5 grid[d[0]][d[1]] = 1; 6 7 for (int i = 0, acc = 0; i < n; i++) 8 grid[i][0] = acc += grid[i][0]; 9 for (int i = 0, acc = 0; i < n; i++) 10 grid[0][i] = acc += grid[0][i]; 11 for (int i = 1; i < n; i++) { 12 for (int j = 1; j < n; j++) { 13 grid[i][j] += grid[i - 1][j] + grid[i][j - 1] - grid[i - 1][j - 1]; 14 } 15 } 16 17 int res = 0; 18 for (const auto &art : artifacts) { 19 const int goal = (art[2] - art[0] + 1) * (art[3] - art[1] + 1); 20 int crnt = grid[art[2]][art[3]]; 21 crnt -= art[0] > 0 ? grid[art[0] - 1][art[3]] : 0; 22 crnt -= art[1] > 0 ? grid[art[2]][art[1] - 1] : 0; 23 crnt += art[0] > 0 && art[1] > 0 ? grid[art[0] - 1][art[1] - 1] : 0; 24 res += goal == crnt; 25 } 26 27 return res; 28 } 29 };