黑格子的数目

You are given two integers m and n representing the dimensions of a 0-indexed m x n grid.

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.

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].

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.

 

Example 1:

Input: m = 3, n = 3, coordinates = [[0,0]]
Output: [3,1,0,0,0]
Explanation: The grid looks like this:

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]. 

Example 2:

Input: m = 3, n = 3, coordinates = [[0,0],[1,1],[0,2]]
Output: [0,2,2,0,0]
Explanation: The grid looks like this:

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].

 

Constraints:

• 2 <= m <= 105
• 2 <= n <= 105
• 0 <= coordinates.length <= 104
• coordinates[i].length == 2
• 0 <= coordinates[i][0] < m
• 0 <= coordinates[i][1] < n
• It is guaranteed that coordinates contains pairwise distinct coordinates.

/*
 * 题目思路:
 * 1. 使用Java Stream API来简化代码结构。
 * 2. 创建一个数组result，长度为5，用来保存恰好包含0到4个黑色格子的块的数量。
 * 3. 遍历coordinates数组，对于每个黑色格子的坐标，将其影响的所有可能包含该格子的2x2块的黑色格子数增加1。
 * 4. 使用stream来统计每个2x2块的黑色格子数，最终统计每个黑色格子数的块的数量。
 */

import java.util.*;
import java.util.stream.Collectors;

public class Solution {
    public int[] countBlackBlocks(int m, int n, int[][] coordinates) {
        int[] result = new int[5];
        Map<String, Integer> blockCount = new HashMap<>();

        Arrays.stream(coordinates).forEach(coord -> {
            int x = coord[0], y = coord[1];
            for (int i = Math.max(0, x - 1); i <= Math.min(x, m - 2); i++) {
                for (int j = Math.max(0, y - 1); j <= Math.min(y, n - 2); j++) {
                    String key = i + "," + j;
                    blockCount.put(key, blockCount.getOrDefault(key, 0) + 1);
                }
            }
        });

        blockCount.values().forEach(count -> result[count]++);

        int totalBlocks = (m - 1) * (n - 1);
        result[0] = totalBlocks - Arrays.stream(result).sum() + result[0];

        return result;
    }
}

该题解首先使用一个集合s来记录所有黑色格子的坐标，以便于后续判断一个格子是否为黑色。接着，遍历所有的黑色格子坐标，并对每个黑色格子坐标进行四种情况的检查：1) 当前格子作为2x2子矩阵左上角；2) 当前格子作为2x2子矩阵右上角；3) 当前格子作为2x2子矩阵左下角；4) 当前格子作为2x2子矩阵右下角。对于每一种情况，根据黑色格子的存在与否统计每个子矩阵中黑色格子的数量，并更新结果数组ans。最后，通过总2x2子矩阵数量减去包含1个及以上黑色格子的子矩阵的数量，来计算完全由白色格子组成的子矩阵的数量。

O(k)

O(k)