2201. Count Artifacts That Can Be Extracted Medium

1/**
2 * [2201] Count Artifacts That Can Be Extracted
3 *
4 * 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 i^th artifact is buried in the subgrid where:
5 * 
6 * 	(r1i, c1i) is the coordinate of the top-left cell of the i^th artifact and
7 * 	(r2i, c2i) is the coordinate of the bottom-right cell of the i^th artifact.
8 * 
9 * 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.
10 * 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.
11 * The test cases are generated such that:
12 * 
13 * 	No two artifacts overlap.
14 * 	Each artifact only covers at most 4 cells.
15 * 	The entries of dig are unique.
16 * 
17 *  
18 * Example 1:
19 * <img alt="" src="https://assets.leetcode.com/uploads/2019/09/16/untitled-diagram.jpg" style="width: 216px; height: 216px;" />
20 * Input: n = 2, artifacts = [[0,0,0,0],[0,1,1,1]], dig = [[0,0],[0,1]]
21 * Output: 1
22 * Explanation: 
23 * The different colors represent different artifacts. Excavated cells are labeled with a 'D' in the grid.
24 * There is 1 artifact that can be extracted, namely the red artifact.
25 * The blue artifact has one part in cell (1,1) which remains uncovered, so we cannot extract it.
26 * Thus, we return 1.
27 * 
28 * Example 2:
29 * <img alt="" src="https://assets.leetcode.com/uploads/2019/09/16/untitled-diagram-1.jpg" style="width: 216px; height: 216px;" />
30 * Input: n = 2, artifacts = [[0,0,0,0],[0,1,1,1]], dig = [[0,0],[0,1],[1,1]]
31 * Output: 2
32 * Explanation: Both the red and blue artifacts have all parts uncovered (labeled with a 'D') and can be extracted, so we return 2. 
33 * 
34 *  
35 * Constraints:
36 * 
37 * 	1 <= n <= 1000
38 * 	1 <= artifacts.length, dig.length <= min(n^2, 10^5)
39 * 	artifacts[i].length == 4
40 * 	dig[i].length == 2
41 * 	0 <= r1i, c1i, r2i, c2i, ri, ci <= n - 1
42 * 	r1i <= r2i
43 * 	c1i <= c2i
44 * 	No two artifacts will overlap.
45 * 	The number of cells covered by an artifact is at most 4.
46 * 	The entries of dig are unique.
47 * 
48 */
49pub struct Solution {}
50
51// problem: https://leetcode.com/problems/count-artifacts-that-can-be-extracted/
52// discuss: https://leetcode.com/problems/count-artifacts-that-can-be-extracted/discuss/?currentPage=1&orderBy=most_votes&query=
53
54// submission codes start here
55
56impl Solution {
57    pub fn dig_artifacts(n: i32, artifacts: Vec<Vec<i32>>, dig: Vec<Vec<i32>>) -> i32 {
58        0
59    }
60}
61
62// submission codes end
63
64#[cfg(test)]
65mod tests {
66    use super::*;
67
68    #[test]
69    fn test_2201() {
70    }
71}
72