2768-黑格子的数目

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:25 2023-09-13 16:06:25 Updated    

给你两个整数 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]
**解释：** 网格图如下：
![](https://assets.leetcode.com/uploads/2023/06/18/screen-shot-2023-06-18-at-44656-am.png)
只有 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]
**解释：** 网格图如下：
![](https://assets.leetcode.com/uploads/2023/06/18/screen-shot-2023-06-18-at-45018-am.png)
有 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 中的坐标对两两互不相同。

下午两点【b站@灵茶山艾府】 直播讲题，欢迎关注！

在 m 和 n 都很大的情况下，网格中有大量的 2\times 2 的子矩阵是没有黑色格子的。只需要考虑有黑色格子的子矩阵。

如果 (x,y) 处有黑色格子，那么子矩阵左上角在 (x-1,y-1),(x-1,y),(x,y-1),(x,y) 都是包含这个黑色格子的，统计这些子矩阵中有多少黑色格子，加到答案中。

代码实现时，注意不要重复统计，可以用哈希表 vis 来记录统计过的子矩阵左上角。

最后不含黑色格子的子矩阵个数就是

(m-1)\cdot (n-1) - \text{len}(\textit{vis})

[sol-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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
[sol-Go]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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 }

复杂度分析

  • 时间复杂度：\mathcal{O}(k)，其中 k 为 coordinates 的长度。
  • 空间复杂度：\mathcal{O}(k)。
 Comments
On this page
2768-黑格子的数目