javascript 解法, 执行用时: 596 ms, 内存消耗: 72.1 MB, 提交时间: 2023-07-10 09:55:11

/**
 * @param {number} m
 * @param {number} n
 * @param {number[][]} coordinates
 * @return {number[]}
 */
var countBlackBlocks = function (m, n, coordinates) {
  const map = new Map();
  const dir = [// 分别以当前坐标作为块左上角，左下角，右上角，右下角，计算出所有涉及到的块的坐标
    [0, 0],
    [0, -1],
    [-1, 0],
    [-1, -1],
  ];

  for (const [x, y] of coordinates) {
    for (const [dx, dy] of dir) {
      const nx = x + dx;
      const ny = y + dy;
      if (nx >= 0 && nx < m - 1 && ny >= 0 && ny < n - 1) {
        const key = `${nx}-${ny}`;
        map.set(key, (map.get(key) || 0) + 1);
      }
    }
  }

  const ans = new Array(5).fill(0);
  for (const [key, val] of map) {
    ans[val]++;
  }
  ans[0] = (m - 1) * (n - 1) - ans.reduce((a, b) => a + b, 0);

  return ans;
};

cpp 解法, 执行用时: 1020 ms, 内存消耗: 242.7 MB, 提交时间: 2023-07-10 09:53:23

/**
 * 哈希枚举
 * 枚举coordinates中的黑色格子, 每个黑色格子最多能使周围的4个块的块内黑格子数加1, 
 * 用哈希记录出现过的块的块内黑格子数.
 **/
class Solution {
public:
    vector<long long> countBlackBlocks(int m, int n, vector<vector<int>> &coordinates) {
        map<pair<int, int>, int> cnt;//块左上角的坐标 -> 块内黑格子数
        int dx[4] = {0, -1, -1, 0};
        int dy[4] = {-1, -1, 0, 0};
        for (auto &p: coordinates) {
            for (int k = 0; k < 4; k++) {
                int nx = p[0] + dx[k];
                int ny = p[1] + dy[k];
                if (nx < 0 || nx >= m - 1 || ny < 0 || ny >= n - 1)
                    continue;
                cnt[{nx, ny}]++;//块左上角的坐标为(nx,ny)的块的块内黑格子数更新
            }
        }
        vector<long long> res(5);
        for (auto &[_, v]: cnt)
            res[v]++;
        res[0] = 1LL * (m - 1) * (n - 1) - accumulate(res.begin() + 1, res.end(), 0);
        return res;
    }
};

golang 解法, 执行用时: 440 ms, 内存消耗: 9.6 MB, 提交时间: 2023-07-10 09:52:20

func countBlackBlocks(m, n int, coordinates [][]int) []int64 {
	type pair struct{ x, y int }
	set := make(map[pair]int, len(coordinates))
	for _, p := range coordinates {
		set[pair{p[0], p[1]}] = 1
	}

	arr := make([]int64, 5)
	vis := make(map[pair]bool, len(set)*4)
	for _, p := range coordinates {
		x, y := p[0], p[1]
		for i := max(x-1, 0); i <= x && i < m-1; i++ {
			for j := max(y-1, 0); j <= y && j < n-1; j++ {
				if !vis[pair{i, j}] {
					vis[pair{i, j}] = true
					cnt := set[pair{i, j}] + set[pair{i, j + 1}] +
						   set[pair{i + 1, j}] + set[pair{i + 1, j + 1}]
					arr[cnt]++
				}
			}
		}
	}
	arr[0] = int64(m-1)*int64(n-1) - int64(len(vis)) // 不含黑格子的块
	return arr
}

func max(a, b int) int { if b > a { return b }; return a }

python3 解法, 执行用时: 1276 ms, 内存消耗: 26.2 MB, 提交时间: 2023-07-10 09:51:45

'''
枚举
只考虑有黑格子的子矩阵，如果(x, y)处有黑格子, 则(x-1, y-1), (x-1, y), (x, y-1),(x,y)的块都包含这个黑格子。
代码实现时，注意不要重复统计，可以用哈希表 vis 来记录统计过的子矩阵左上角。
'''
class Solution:
    def countBlackBlocks(self, m: int, n: int, coordinates: List[List[int]]) -> List[int]:
        s = set(map(tuple, coordinates))
        arr = [0] * 5
        vis = set()
        for x, y in coordinates:
            for i in range(max(x - 1, 0), min(x + 1, m - 1)):
                for j in range(max(y - 1, 0), min(y + 1, n - 1)):
                    if (i, j) not in vis:
                        vis.add((i, j))
                        cnt = ((i, j) in s) + ((i, j + 1) in s) + \
                              ((i + 1, j) in s) + ((i + 1, j + 1) in s)
                        arr[cnt] += 1
        arr[0] = (m - 1) * (n - 1) - len(vis)
        return arr