2768. Number of Black Blocks Medium

1/**
2 * [2768] Number of Black Blocks
3 *
4 * You are given two integers m and n representing the dimensions of a 0-indexed m x n grid.
5 * You are also given a 0-indexed 2D integer matrix coordinates, where coordinates[i] = [x, y] indicates that the cell with coordinates [x, y] is colored black. All cells in the grid that do not appear in coordinates are white.
6 * A block is defined as a 2 x 2 submatrix of the grid. More formally, a block with cell [x, y] as its top-left corner where 0 <= x < m - 1 and 0 <= y < n - 1 contains the coordinates [x, y], [x + 1, y], [x, y + 1], and [x + 1, y + 1].
7 * Return a 0-indexed integer array arr of size 5 such that arr[i] is the number of blocks that contains exactly i black cells.
8 *  
9 * <strong class="example">Example 1:
10 * 
11 * Input: m = 3, n = 3, coordinates = [[0,0]]
12 * Output: [3,1,0,0,0]
13 * Explanation: The grid looks like this:
14 * <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;" />
15 * There is only 1 block with one black cell, and it is the block starting with cell [0,0].
16 * The other 3 blocks start with cells [0,1], [1,0] and [1,1]. They all have zero black cells. 
17 * Thus, we return [3,1,0,0,0]. 
18 * 
19 * <strong class="example">Example 2:
20 * 
21 * Input: m = 3, n = 3, coordinates = [[0,0],[1,1],[0,2]]
22 * Output: [0,2,2,0,0]
23 * Explanation: The grid looks like this:
24 * <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;" />
25 * There are 2 blocks with two black cells (the ones starting with cell coordinates [0,0] and [0,1]).
26 * The other 2 blocks have starting cell coordinates of [1,0] and [1,1]. They both have 1 black cell.
27 * Therefore, we return [0,2,2,0,0].
28 * 
29 *  
30 * Constraints:
31 * 
32 * 	2 <= m <= 10^5
33 * 	2 <= n <= 10^5
34 * 	0 <= coordinates.length <= 10^4
35 * 	coordinates[i].length == 2
36 * 	0 <= coordinates[i][0] < m
37 * 	0 <= coordinates[i][1] < n
38 * 	It is guaranteed that coordinates contains pairwise distinct coordinates.
39 * 
40 */
41pub struct Solution {}
42
43// problem: https://leetcode.com/problems/number-of-black-blocks/
44// discuss: https://leetcode.com/problems/number-of-black-blocks/discuss/?currentPage=1&orderBy=most_votes&query=
45
46// submission codes start here
47
48impl Solution {
49    pub fn count_black_blocks(m: i32, n: i32, coordinates: Vec<Vec<i32>>) -> Vec<i64> {
50        
51    }
52}
53
54// submission codes end
55
56#[cfg(test)]
57mod tests {
58    use super::*;
59
60    #[test]
61    fn test_2768() {
62    }
63}
64