统计可以提取的工件

2201. 统计可以提取的工件

存在一个 n x n 大小、下标从 0 开始的网格，网格中埋着一些工件。给你一个整数 n 和一个下标从 0 开始的二维整数数组 artifacts ，artifacts 描述了矩形工件的位置，其中 artifacts[i] = [r1_i, c1_i, r2_i, c2_i] 表示第 i 个工件在子网格中的填埋情况：

(r1_i, c1_i) 是第 i 个工件左上单元格的坐标，且
(r2_i, c2_i) 是第 i 个工件右下单元格的坐标。

你将会挖掘网格中的一些单元格，并清除其中的填埋物。如果单元格中埋着工件的一部分，那么该工件这一部分将会裸露出来。如果一个工件的所有部分都都裸露出来，你就可以提取该工件。

给你一个下标从 0 开始的二维整数数组 dig ，其中 dig[i] = [r_i, c_i] 表示你将会挖掘单元格 (r_i, c_i) ，返回你可以提取的工件数目。

生成的测试用例满足：

不存在重叠的两个工件。
每个工件最多只覆盖 4 个单元格。
dig 中的元素互不相同。

示例 1：

输入：n = 2, artifacts = [[0,0,0,0],[0,1,1,1]], dig = [[0,0],[0,1]]
输出：1
解释： 
不同颜色表示不同的工件。挖掘的单元格用 'D' 在网格中进行标记。
有 1 个工件可以提取，即红色工件。
蓝色工件在单元格 (1,1) 的部分尚未裸露出来，所以无法提取该工件。
因此，返回 1 。

示例 2：

输入：n = 2, artifacts = [[0,0,0,0],[0,1,1,1]], dig = [[0,0],[0,1],[1,1]]
输出：2
解释：红色工件和蓝色工件的所有部分都裸露出来（用 'D' 标记），都可以提取。因此，返回 2 。

提示：

1 <= n <= 1000
1 <= artifacts.length, dig.length <= min(n², 10⁵)
artifacts[i].length == 4
dig[i].length == 2
0 <= r1_i, c1_i, r2_i, c2_i, r_i, c_i <= n - 1
r1_i <= r2_i
c1_i <= c2_i
不存在重叠的两个工件
每个工件最多只覆盖 4 个单元格
dig 中的元素互不相同

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: int digArtifacts(int n, vector<vector<int>>& artifacts, vector<vector<int>>& dig) { } };

python3 解法, 执行用时: 320 ms, 内存消耗: 61.3 MB, 提交时间: 2023-06-01 09:56:11

class Solution:
    def digArtifacts(self, n: int, artifacts: List[List[int]], dig: List[List[int]]) -> int:
        setdig = {tuple(p) for p in dig}
        return [all((r, c) in setdig for r in range(r1, r2 + 1) for c in range(c1, c2 + 1)) for r1, c1, r2, c2 in artifacts].count(True)

java 解法, 执行用时: 3 ms, 内存消耗: 112.9 MB, 提交时间: 2023-06-01 09:55:46

class Solution {
    public int digArtifacts(int n, int[][] artifacts, int[][] dig) {
        //记录单元格是否已经裸露
        boolean[] f = new boolean[n * n];
        for (int[] d : dig) {
            int idx = d[0] * n + d[1];
            f[idx] = true;
        }

        int ans = 0;
        for (int[] art : artifacts) {
            // 是否裸露
            boolean flag = true;
            for (int r = art[0]; r <= art[2] && flag; r++) {
                for (int c = art[1]; c <= art[3] && flag; c++) {
                    int idx = r * n + c;
                    flag = f[idx];
                }
            }

            // 范围内所有单元格都已经裸露
            if (flag) ans++;
        }

        return ans;
    }
}

python3 解法, 执行用时: 232 ms, 内存消耗: 61.3 MB, 提交时间: 2023-06-01 09:55:24

class Solution:
    def digArtifacts(self, n: int, artifacts: List[List[int]], dig: List[List[int]]) -> int:
        valid = {tuple(pos) for pos in dig}
        
        ans = 0
        for (r1, c1, r2, c2) in artifacts:
            check = True
            for r in range(r1, r2 + 1):
                for c in range(c1, c2 + 1):
                    if (r, c) not in valid:
                        check = False
                        break
                if not check:
                    break
            
            if check:
                ans += 1

        return ans

golang 解法, 执行用时: 300 ms, 内存消耗: 34.6 MB, 提交时间: 2023-06-01 09:55:05

/**
 * 暴力枚举 + 哈希表
 * 由于每个工件最多只覆盖 4 个单元格，可以用哈希表记录哪些单元格被挖掘过，
 * 然后暴力检查每个工件覆盖的格子是否被挖过。
 * 第一个参数多余的
 **/
func digArtifacts(_ int, artifacts [][]int, dig [][]int) (ans int) {
	type pair struct{ x, y int }
	d := map[pair]bool{}
	for _, p := range dig {
		d[pair{p[0], p[1]}] = true
	}
next:
	for _, art := range artifacts {
		for i := art[0]; i <= art[2]; i++ {
			for j := art[1]; j <= art[3]; j++ {
				if !d[pair{i, j}] {
					continue next
				}
			}
		}
		ans++
	}
	return
}

上一题

下一题

详情