[LeetCode] Count Artifacts That Can Be Extracted

2201. Count Artifacts That Can Be Extracted

There is an n x n 0-indexed grid with some artifacts buried in it. You are given the integer n and a 0-indexed 2D integer array artifacts describing the positions of the rectangular artifacts where artifacts[i] = [r1i, c1i, r2i, c2i] denotes that the ith artifact is buried in the subgrid where:

  • (r1i, c1i) is the coordinate of the top-left cell of the ith artifact and
  • (r2i, c2i) is the coordinate of the bottom-right cell of the ith artifact.

You will excavate some cells of the grid and remove all the mud from them. If the cell has a part of an artifact buried underneath, it will be uncovered. If all the parts of an artifact are uncovered, you can extract it.

Given a 0-indexed 2D integer array dig where dig[i] = [ri, ci] indicates that you will excavate the cell (ri, ci), return the number of artifacts that you can extract.

The test cases are generated such that:

  • No two artifacts overlap.
  • Each artifact only covers at most 4 cells.
  • The entries of dig are unique.
  • simulation solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
void marking(int id, vector<vector<int>>& matrix, vector<int>& arti, vector<int>& artiSize) {
for(int i = arti[0]; i <= arti[2]; i++)
for(int j = arti[1]; j <= arti[3]; j++) {
artiSize[id]++;
matrix[i][j] = id;
}
}
public:
int digArtifacts(int n, vector<vector<int>>& artifacts, vector<vector<int>>& dig) {
vector<vector<int>> matrix(n, vector<int>(n,0));
vector<int> artiSize(artifacts.size() + 1, 0);
for(int i = 0; i < artifacts.size(); i++) {
marking(i + 1, matrix, artifacts[i], artiSize);
}
for(auto d : dig) {
artiSize[matrix[d[0]][d[1]]]--;
matrix[d[0]][d[1]] = 0;
}
int res = 0;
for(int i = 1; i < artiSize.size(); i++) {
if(artiSize[i] == 0) res++;
}
return res;
}
};
  • hash set solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
int digArtifacts(int n, vector<vector<int>>& artifacts, vector<vector<int>>& dig) {
unordered_set<int> us;
for(auto d : dig) {
us.insert(d[0] * 1000 + d[1]);
}
int res = 0;
for(auto arti : artifacts) {
bool find = true;
for (int i = arti[0]; i <= arti[2] and find; i++) {
for (int j = arti[1]; j <= arti[3] and find; j++) {
if (!us.count(i * 1000 + j)) find = false;
}
}
if(find) res++;
}
return res;
}
};
Author: Song Hayoung
Link: https://songhayoung.github.io/2022/03/13/PS/LeetCode/count-artifacts-that-can-be-extracted/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.