#2201

Count Artifacts That Can Be Extracted

specialist · 815 · lc medium +31 · verified · 57.1% accepted · 225 likes · top 52%

Description

There is an n x n 0-indexed grid with buried artifacts. You are given the integer n and a 0-indexed 2D integer array artifacts where artifacts[i] = [r1i, c1i, r2i, c2i] describes the i^th artifact:

- (r1i, c1i) is the top-left cell of the artifact.

- (r2i, c2i) is the bottom-right cell.

You excavate certain cells. If all cells of an artifact are excavated, you can extract it.

Given a 0-indexed 2D integer array dig where dig[i] = [ri, ci] marks excavated cells, return the number of artifacts you can extract.

The test cases guarantee:

- No two artifacts overlap.

- Each artifact covers at most 4 cells.

- All entries of dig are unique.

Example 1:

Input: n = 2, artifacts = [[0,0,0,0],[0,1,1,1]], dig = [[0,0],[0,1]]

Output: 1

Explanation:

The different colors represent different artifacts. Excavated cells are labeled with a 'D' in the grid.

There is 1 artifact that can be extracted, namely the red artifact.

The blue artifact has one part in cell (1,1) which remains uncovered, so we cannot extract it.

Thus, we return 1.

Example 2:

Input: n = 2, artifacts = [[0,0,0,0],[0,1,1,1]], dig = [[0,0],[0,1],[1,1]]

Output: 2

Explanation: Both the red and blue artifacts have all parts uncovered (labeled with a 'D') and can be extracted, so we return 2.

Code

1

2

3

class Solution:
    def digArtifacts(self, n: int, artifacts: List[List[int]], dig: List[List[int]]) -> int:

class Solution:
    def digArtifacts(self, n: int, artifacts: List[List[int]], dig: List[List[int]]) -> int: