count-artifacts-that-can-be-extracted

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

There is an <code>n x n</code> 0-indexed grid with some artifacts buried in it. You are given the integer <code>n</code> and a 0-indexed 2D integer array <code>artifacts</code> describing the positions of the rectangular artifacts where <code>artifacts[i] = [r1i, c1i, r2i, c2i]</code> denotes that the <code>ith</code> artifact is buried in the subgrid where:

<ul>
	<li><code>(r1i, c1i)</code> is the coordinate of the top-left cell of the <code>ith</code> artifact and</li>
	<li><code>(r2i, c2i)</code> is the coordinate of the bottom-right cell of the <code>ith</code> artifact.</li>
</ul>

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 <code>dig</code> where <code>dig[i] = [ri, ci]</code> indicates that you will excavate the cell <code>(ri, ci)</code>, return the number of artifacts that you can extract.

The test cases are generated such that:

<ul>
	<li>No two artifacts overlap.</li>
	<li>Each artifact only covers at most <code>4</code> cells.</li>
	<li>The entries of <code>dig</code> are unique.</li>
</ul>

&nbsp;
Example 1:
<img alt="" src="https://assets.leetcode.com/uploads/2019/09/16/untitled-diagram.jpg" style="width: 216px; height: 216px;" />
<pre>
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 &#39;D&#39; 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.
</pre>

Example 2:
<img alt="" src="https://assets.leetcode.com/uploads/2019/09/16/untitled-diagram-1.jpg" style="width: 216px; height: 216px;" />
<pre>
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 &#39;D&#39;) and can be extracted, so we return 2. 
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= n &lt;= 1000</code></li>
	<li><code>1 &lt;= artifacts.length, dig.length &lt;= min(n2, 105)</code></li>
	<li><code>artifacts[i].length == 4</code></li>
	<li><code>dig[i].length == 2</code></li>
	<li><code>0 &lt;= r1i, c1i, r2i, c2i, ri, ci &lt;= n - 1</code></li>
	<li><code>r1i &lt;= r2i</code></li>
	<li><code>c1i &lt;= c2i</code></li>
	<li>No two artifacts will overlap.</li>
	<li>The number of cells covered by an artifact is at most <code>4</code>.</li>
	<li>The entries of <code>dig</code> are unique.</li>
</ul>

digArtifacts

Count Artifacts That Can Be Extracted

Maximal Square

maximal-square

最大正方形

Array

Hash Table

Simulation

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

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

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

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

生成的测试用例满足：

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

&nbsp;

示例 1：
<img alt="" src="https://assets.leetcode.com/uploads/2019/09/16/untitled-diagram.jpg" style="width: 216px; height: 216px;">
<pre>输入：n = 2, artifacts = [[0,0,0,0],[0,1,1,1]], dig = [[0,0],[0,1]]
输出：1
解释： 
不同颜色表示不同的工件。挖掘的单元格用 'D' 在网格中进行标记。
有 1 个工件可以提取，即红色工件。
蓝色工件在单元格 (1,1) 的部分尚未裸露出来，所以无法提取该工件。
因此，返回 1 。
</pre>

示例 2：
<img alt="" src="https://assets.leetcode.com/uploads/2019/09/16/untitled-diagram-1.jpg" style="width: 216px; height: 216px;">
<pre>输入：n = 2, artifacts = [[0,0,0,0],[0,1,1,1]], dig = [[0,0],[0,1],[1,1]]
输出：2
解释：红色工件和蓝色工件的所有部分都裸露出来（用 'D' 标记），都可以提取。因此，返回 2 。 
</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= n &lt;= 1000</code></li>
	<li><code>1 &lt;= artifacts.length, dig.length &lt;= min(n2, 105)</code></li>
	<li><code>artifacts[i].length == 4</code></li>
	<li><code>dig[i].length == 2</code></li>
	<li><code>0 &lt;= r1i, c1i, r2i, c2i, ri, ci &lt;= n - 1</code></li>
	<li><code>r1i &lt;= r2i</code></li>
	<li><code>c1i &lt;= c2i</code></li>
	<li>不存在重叠的两个工件</li>
	<li>每个工件 最多 只覆盖 <code>4</code> 个单元格</li>
	<li><code>dig</code> 中的元素互不相同</li>
</ul>