There is an n x n0-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.

Input: n =2, artifacts =[[0,0,0,0],[0,1,1,1]], dig =[[0,0],[0,1]]Output: 1Explanation:
The different colors represent different artifacts. Excavated cells are labeled with a 'D'in the grid.There is1 artifact that can be extracted, namely the red artifact.The blue artifact has one part incell(1,1) which remains uncovered, so we cannot extract it.Thus, we return1.

Input: n =2, artifacts =[[0,0,0,0],[0,1,1,1]], dig =[[0,0],[0,1],[1,1]]Output: 2Explanation: Both the red and blue artifacts have all parts uncovered(labeled with a 'D') and can be extracted, so we return2.
Each artifact covers a set of cells. If all the cells of an artifact are dug, the artifact can be extracted. We can use a set to record all dug cells and check for each artifact if all its cells are in the set.
classSolution {
public:int digArtifacts(int n, vector<vector<int>>& artifacts, vector<vector<int>>& dig) {
set<pair<int, int>> dug;
for (auto& d : dig) dug.insert({d[0], d[1]});
int ans =0;
for (auto& a : artifacts) {
bool ok = true;
for (int i = a[0]; i <= a[2]; ++i) {
for (int j = a[1]; j <= a[3]; ++j) {
if (!dug.count({i, j})) ok = false;
}
}
if (ok) ++ans;
}
return ans;
}
};
classSolution {
publicintdigArtifacts(int n, int[][] artifacts, int[][] dig) {
Set<String> dug =new HashSet<>();
for (int[] d : dig) dug.add(d[0]+","+ d[1]);
int ans = 0;
for (int[] a : artifacts) {
boolean ok =true;
for (int i = a[0]; i <= a[2]; ++i) {
for (int j = a[1]; j <= a[3]; ++j) {
if (!dug.contains(i +","+ j)) ok =false;
}
}
if (ok) ans++;
}
return ans;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
classSolution {
fundigArtifacts(n: Int, artifacts: Array<IntArray>, dig: Array<IntArray>): Int {
val dug = mutableSetOf<Pair<Int, Int>>()
for (d in dig) dug.add(Pair(d[0], d[1]))
var ans = 0for (a in artifacts) {
var ok = truefor (i in a[0]..a[2]) {
for (j in a[1]..a[3]) {
if (Pair(i, j) !in dug) ok = false }
}
if (ok) ans++ }
return ans
}
}
1
2
3
4
5
6
7
8
classSolution:
defdigArtifacts(self, n: int, artifacts: list[list[int]], dig: list[list[int]]) -> int:
dug = set((r, c) for r, c in dig)
ans =0for r1, c1, r2, c2 in artifacts:
if all((i, j) in dug for i in range(r1, r2+1) for j in range(c1, c2+1)):
ans +=1return ans
impl Solution {
pubfndig_artifacts(_n: i32, artifacts: Vec<Vec<i32>>, dig: Vec<Vec<i32>>) -> i32 {
use std::collections::HashSet;
let dug: HashSet<(i32, i32)>= dig.iter().map(|d| (d[0], d[1])).collect();
letmut ans =0;
for a in artifacts {
letmut ok =true;
for i in a[0]..=a[2] {
for j in a[1]..=a[3] {
if!dug.contains(&(i, j)) {
ok =false;
}
}
}
if ok {
ans +=1;
}
}
ans
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
classSolution {
digArtifacts(n: number, artifacts: number[][], dig: number[][]):number {
constdug=newSet(dig.map(([r, c]) =>r+','+c));
letans=0;
for (const [r1, c1, r2, c2] ofartifacts) {
letok=true;
for (leti=r1; i<=r2; ++i) {
for (letj=c1; j<=c2; ++j) {
if (!dug.has(i+','+j)) ok=false;
}
}
if (ok) ans++;
}
returnans;
}
}
⏰ Time complexity: O(A * S), where A is the number of artifacts and S is the maximum number of cells per artifact (at most 4), plus O(D) for the number of dig cells.
🧺 Space complexity: O(D), for the set of dug cells.