5203. 统计可以提取的工件

刷题笔记

发布日期: 2022-03-14

5203. 统计可以提取的工件

题目描述

示例 1：

输入：n = 2, artifacts = [[0,0,0,0],[0,1,1,1]], dig = [[0,0],[0,1]]

输出：1

解释：

不同颜色表示不同的工件。挖掘的单元格用 ‘D’ 在网格中进行标记。有 1 个工件可以提取，即红色工件。蓝色工件在单元格 (1,1) 的部分尚未裸露出来，所以无法提取该工件。因此，返回 1 。

nXn大小的网格， artifacts[i]表示了工件i 在网格中的位置前两个是工件左上位置坐标，后两个是右下位置坐标。dg[i] 表示挖掘的网格位置求能挖到多少工件。

官方题目描述：

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

(r1i, c1i) 是第 i 个工件左上单元格的坐标，且(r2i, c2i) 是第 i 个工件右下单元格的坐标。

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

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

生成的测试用例满足：

不存在重叠的两个工件。

每个工件最多只覆盖 4 个单元格。

dig 中的元素互不相同。

基本思路

暴力模拟

首先遍历 dig数组，将挖掘到的网格位置置1

然后遍历工件位置数组，如果此工件包含的网格位置都为1，那么该工件被发掘到，答案+1

class Solution {
public:
    int digArtifacts(int n, vector<vector<int>>& artifacts, vector<vector<int>>& dig) {
        int ans = 0;
        vector<vector<int>> grid(n,vector<int>(n,0));

        for(auto d : dig){
             grid[d[0]][d[1]] = 1;
        }
        
        for(auto art : artifacts){
            int flag = 1;
            for(int i = art[0];i<=art[2];++i){
                for(int j = art[1];j<= art[3];++j){
                   if(grid[i][j] == 0) flag = 0;
                }
            }
            
            if(flag) ans++;
        
        }
        
        return ans;
    }
};