leetcode

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 };