number-of-black-blocks

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given two integers <code>m</code> and <code>n</code> representing the dimensions of a&nbsp;0-indexed&nbsp;<code>m x n</code> grid.

You are also given a 0-indexed 2D integer matrix <code>coordinates</code>, where <code>coordinates[i] = [x, y]</code> indicates that the cell with coordinates <code>[x, y]</code> is colored black. All cells in the grid that do not appear in <code>coordinates</code> are white.

A block is defined as a <code>2 x 2</code> submatrix of the grid. More formally, a block with cell <code>[x, y]</code> as its top-left corner where <code>0 &lt;= x &lt; m - 1</code> and <code>0 &lt;= y &lt; n - 1</code> contains the coordinates <code>[x, y]</code>, <code>[x + 1, y]</code>, <code>[x, y + 1]</code>, and <code>[x + 1, y + 1]</code>.

Return a 0-indexed integer array <code>arr</code> of size <code>5</code> such that <code>arr[i]</code> is the number of blocks that contains exactly <code>i</code> black cells.

&nbsp;
Example 1:

<pre>
Input: m = 3, n = 3, coordinates = [[0,0]]
Output: [3,1,0,0,0]
Explanation: The grid looks like this:
<img alt="" src="https://assets.leetcode.com/uploads/2023/06/18/screen-shot-2023-06-18-at-44656-am.png" style="width: 150px; height: 128px;" />
There is only 1 block with one black cell, and it is the block starting with cell [0,0].
The other 3 blocks start with cells [0,1], [1,0] and [1,1]. They all have zero black cells. 
Thus, we return [3,1,0,0,0]. 
</pre>

Example 2:

<pre>
Input: m = 3, n = 3, coordinates = [[0,0],[1,1],[0,2]]
Output: [0,2,2,0,0]
Explanation: The grid looks like this:
<img alt="" src="https://assets.leetcode.com/uploads/2023/06/18/screen-shot-2023-06-18-at-45018-am.png" style="width: 150px; height: 128px;" />
There are 2 blocks with two black cells (the ones starting with cell coordinates [0,0] and [0,1]).
The other 2 blocks have starting cell coordinates of [1,0] and [1,1]. They both have 1 black cell.
Therefore, we return [0,2,2,0,0].
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>2 &lt;= m &lt;= 105</code></li>
	<li><code>2 &lt;= n &lt;= 105</code></li>
	<li><code>0 &lt;= coordinates.length &lt;= 104</code></li>
	<li><code>coordinates[i].length == 2</code></li>
	<li><code>0 &lt;= coordinates[i][0] &lt; m</code></li>
	<li><code>0 &lt;= coordinates[i][1] &lt; n</code></li>
	<li>It is guaranteed that <code>coordinates</code> contains pairwise distinct coordinates.</li>
</ul>

countBlackBlocks

Number of Black Blocks

Array

Hash Table

Enumeration

给你两个整数&nbsp;<code>m</code> 和&nbsp;<code>n</code>&nbsp;，表示一个下标从 0&nbsp;开始的&nbsp;<code>m x n</code>&nbsp;的网格图。

给你一个下标从 0&nbsp;开始的二维整数矩阵&nbsp;<code>coordinates</code>&nbsp;，其中&nbsp;<code>coordinates[i] = [x, y]</code>&nbsp;表示坐标为&nbsp;<code>[x, y]</code>&nbsp;的格子是 黑色的&nbsp;，所有没出现在&nbsp;<code>coordinates</code>&nbsp;中的格子都是 白色的。

一个块定义为网格图中&nbsp;<code>2 x 2</code>&nbsp;的一个子矩阵。更正式的，对于左上角格子为 <code>[x, y]</code> 的块，其中 <code>0 &lt;= x &lt; m - 1</code> 且&nbsp;<code>0 &lt;= y &lt; n - 1</code> ，包含坐标为&nbsp;<code>[x, y]</code>&nbsp;，<code>[x + 1, y]</code>&nbsp;，<code>[x, y + 1]</code>&nbsp;和&nbsp;<code>[x + 1, y + 1]</code>&nbsp;的格子。

请你返回一个下标从 0&nbsp;开始长度为 <code>5</code>&nbsp;的整数数组&nbsp;<code>arr</code>&nbsp;，<code>arr[i]</code>&nbsp;表示恰好包含&nbsp;<code>i</code>&nbsp;个&nbsp;黑色&nbsp;格子的块的数目。

&nbsp;

示例 1：

<pre>
输入：m = 3, n = 3, coordinates = [[0,0]]
输出：[3,1,0,0,0]
解释：网格图如下：
<img alt="" src="https://assets.leetcode.com/uploads/2023/06/18/screen-shot-2023-06-18-at-44656-am.png" style="width: 150px; height: 128px;" />
只有 1 个块有一个黑色格子，这个块是左上角为 [0,0] 的块。
其他 3 个左上角分别为 [0,1] ，[1,0] 和 [1,1] 的块都有 0 个黑格子。
所以我们返回 [3,1,0,0,0] 。
</pre>

示例 2：

<pre>
输入：m = 3, n = 3, coordinates = [[0,0],[1,1],[0,2]]
输出：[0,2,2,0,0]
解释：网格图如下：
<img alt="" src="https://assets.leetcode.com/uploads/2023/06/18/screen-shot-2023-06-18-at-45018-am.png" style="width: 150px; height: 128px;" />
有 2 个块有 2 个黑色格子（左上角格子分别为 [0,0] 和 [0,1]）。
左上角为 [1,0] 和 [1,1] 的两个块，都有 1 个黑格子。
所以我们返回 [0,2,2,0,0] 。
</pre>

&nbsp;

提示：

<ul>
	<li><code>2 &lt;= m &lt;= 105</code></li>
	<li><code>2 &lt;= n &lt;= 105</code></li>
	<li><code>0 &lt;= coordinates.length &lt;= 104</code></li>
	<li><code>coordinates[i].length == 2</code></li>
	<li><code>0 &lt;= coordinates[i][0] &lt; m</code></li>
	<li><code>0 &lt;= coordinates[i][1] &lt; n</code></li>
	<li><code>coordinates</code>&nbsp;中的坐标对两两互不相同。</li>
</ul>