Question

2768. 黑格子的数目

English Version

题目描述

给你两个整数 m 和 n ，表示一个下标从 0 开始的 m x n 的网格图。

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

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

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

 

示例 1：

输入：m = 3, n = 3, coordinates = [[0,0]]
输出：[3,1,0,0,0]
解释：网格图如下：

只有 1 个块有一个黑色格子，这个块是左上角为 [0,0] 的块。
其他 3 个左上角分别为 [0,1] ，[1,0] 和 [1,1] 的块都有 0 个黑格子。
所以我们返回 [3,1,0,0,0] 。

示例 2：

输入：m = 3, n = 3, coordinates = [[0,0],[1,1],[0,2]]
输出：[0,2,2,0,0]
解释：网格图如下：

有 2 个块有 2 个黑色格子（左上角格子分别为 [0,0] 和 [0,1]）。
左上角为 [1,0] 和 [1,1] 的两个块，都有 1 个黑格子。
所以我们返回 [0,2,2,0,0] 。

 

提示：

• 2 <= m <= 105
• 2 <= n <= 105
• 0 <= coordinates.length <= 104
• coordinates[i].length == 2
• 0 <= coordinates[i][0] < m
• 0 <= coordinates[i][1] < n
• coordinates 中的坐标对两两互不相同。

解法

方法一：哈希表计数

对于每个 $2 \times 2$ 的子矩阵，我们可以用其左上角的坐标 $(x, y)$ 来表示它。

而对于每个黑格子 $(x, y)$，它对 $4$ 个子矩阵的贡献为 $1$，即矩阵 $(x - 1, y - 1)$, $(x - 1, y)$, $(x, y - 1)$, $(x, y)$。

因此，我们遍历所有的黑格子，然后累计每个子矩阵中黑格子的个数，记录在哈希表 $cnt$ 中。

最后，我们遍历 $cnt$ 中的所有值（大于 $0$），统计其出现的次数，记录在答案数组 $ans$ 中，而 $ans[0]$ 则表示没有黑格子的子矩阵的个数，值为 $(m - 1) \times (n - 1) - \sum_{i = 1}^4 ans[i]$。

时间复杂度 $O(l)$，空间复杂度 $O(l)$，其中 $l$ 为 $coordinates$ 的长度。

class Solution:
  def countBlackBlocks(
    self, m: int, n: int, coordinates: List[List[int]]
  ) -> List[int]:
    cnt = Counter()
    for x, y in coordinates:
      for a, b in pairwise((0, 0, -1, -1, 0)):
        i, j = x + a, y + b
        if 0 <= i < m - 1 and 0 <= j < n - 1:
          cnt[(i, j)] += 1
    ans = [0] * 5
    for x in cnt.values():
      ans[x] += 1
    ans[0] = (m - 1) * (n - 1) - len(cnt.values())
    return ans

class Solution {
  public long[] countBlackBlocks(int m, int n, int[][] coordinates) {
    Map<Long, Integer> cnt = new HashMap<>(coordinates.length);
    int[] dirs = {0, 0, -1, -1, 0};
    for (var e : coordinates) {
      int x = e[0], y = e[1];
      for (int k = 0; k < 4; ++k) {
        int i = x + dirs[k], j = y + dirs[k + 1];
        if (i >= 0 && i < m - 1 && j >= 0 && j < n - 1) {
          cnt.merge(1L * i * n + j, 1, Integer::sum);
        }
      }
    }
    long[] ans = new long[5];
    ans[0] = (m - 1L) * (n - 1);
    for (int x : cnt.values()) {
      ++ans[x];
      --ans[0];
    }
    return ans;
  }
}

class Solution {
public:
  vector<long long> countBlackBlocks(int m, int n, vector<vector<int>>& coordinates) {
    unordered_map<long long, int> cnt;
    int dirs[5] = {0, 0, -1, -1, 0};
    for (auto& e : coordinates) {
      int x = e[0], y = e[1];
      for (int k = 0; k < 4; ++k) {
        int i = x + dirs[k], j = y + dirs[k + 1];
        if (i >= 0 && i < m - 1 && j >= 0 && j < n - 1) {
          ++cnt[1LL * i * n + j];
        }
      }
    }
    vector<long long> ans(5);
    ans[0] = (m - 1LL) * (n - 1);
    for (auto& [_, x] : cnt) {
      ++ans[x];
      --ans[0];
    }
    return ans;
  }
};

func countBlackBlocks(m int, n int, coordinates [][]int) []int64 {
  cnt := map[int64]int{}
  dirs := [5]int{0, 0, -1, -1, 0}
  for _, e := range coordinates {
    x, y := e[0], e[1]
    for k := 0; k < 4; k++ {
      i, j := x+dirs[k], y+dirs[k+1]
      if i >= 0 && i < m-1 && j >= 0 && j < n-1 {
        cnt[int64(i*n+j)]++
      }
    }
  }
  ans := make([]int64, 5)
  ans[0] = int64((m - 1) * (n - 1))
  for _, x := range cnt {
    ans[x]++
    ans[0]--
  }
  return ans
}

function countBlackBlocks(m: number, n: number, coordinates: number[][]): number[] {
  const cnt: Map<number, number> = new Map();
  const dirs: number[] = [0, 0, -1, -1, 0];
  for (const [x, y] of coordinates) {
    for (let k = 0; k < 4; ++k) {
      const [i, j] = [x + dirs[k], y + dirs[k + 1]];
      if (i >= 0 && i < m - 1 && j >= 0 && j < n - 1) {
        const key = i * n + j;
        cnt.set(key, (cnt.get(key) || 0) + 1);
      }
    }
  }
  const ans: number[] = Array(5).fill(0);
  ans[0] = (m - 1) * (n - 1);
  for (const [_, x] of cnt) {
    ++ans[x];
    --ans[0];
  }
  return ans;
}