求问一道算法题

刚刚做一个OA， 遇到一道题，

大概是这样的
给长度cols, 高度cols matrixs,  给你一个list 告诉你哪些ROW,COL是黑的   然后以二x二的正方形扫整个matrixs  返回含黑色点的数量的正方形数  eg 含0 黑色点的2x2 方形2个,一个黑色点的方格有三‍‍‍‌‌‍‍‍‌‍‌‍‍‌‍‍‌‌‍‌个    return【0：2，1：3，2:4, 3:5,4:4】


除了brute force没想到好的办法 用brute force只过了两个test case 其他TLE
凭着印象搜题没搜到
请问这道题有lc相似题吗？ 或者可以告诉我better solution吗
感谢！

稀疏矩阵的话，开个哈希表，对于每个非零的点，相应四个2x2正方形的值+1，O(4N)应该不会TLE了

感觉可以sort 那个黑点list用正方形的特性写 不一定对 没细想

每加一个黑点，4个正方形val+1，剩下就是维护每一个方块的val和更新每一类个数

蠡口一三一四?

是不是可以试试另一种方向 就是看以每一个黑点为左上/左下/右上/右下角的正方形，每一个分别包含几个黑点，然后加到各自的类里面。但是要去重。如果黑点数太多就反过来数包含各种白点数的正方形。1白=3黑

感觉可以sort所有点key1是行坐标相等的话key2是列坐标。然后列举出所有方块的可能起始行。比如所有方块在第3 7 8 9那可能起始行就是2 3 6 7 8 9。

然后遍历每个可能起始行，比如8就看所有在7，8里的黑点，用two pointer 初始化指两行的第一个快，每次前进落后的那个pointer。特殊处理一下某一行是空。

假设有n个块这样的复杂度应该是nlogn，不知道还有没更快的

289生命游戏可以看看

感觉是个数学题 题意要求采样方格->黑点的对应关系，但是有没有一个公式，体现从黑点->到采样方格（可能不止一个）的关系？如果有的话只需要再弄一个类似vis数组的东西记录这个采样方格有没有被记录过就好了... 我乱说的（逃

没仔细想，因为没看懂你的题目。比如说一共就一个黑点，根据位置不同，会有四个2x2方块可以扫到它，到底算几个？
1
*_
__

2
_*
__

3
__
*_

4
__
_*

. ----
要我做，就顺着扫描一次所有黑点，对每个点周围的点进行统计，同时把已经扫描过的点放到去重map里面，避免重复统计，这样应该是线性时间复杂度