526互联

LeetCode/黑格子的数目

发布时间 2023-07-09 00:36:19作者: 失控D大白兔

一个块定义为网格图中 2 x 2 的一个子矩阵
请你返回一个下标从 0 开始长度为 5 的整数数组 arr ，arr[i] 表示恰好包含 i 个 黑色格子的块的数目

1. 搜索黑格子周围格子

class Solution {
public:
    int dir[4][2] = {{-1,-1},{-1,0},{0,-1},{0,0}};
    int next[4][2] = {{0,0},{0,1},{1,0},{1,1}};
    vector<long long> countBlackBlocks(int m, int n, vector<vector<int>>& coordinates) {
        //他们的和为 (n-1)*(m-1)
        set<long long> s;
        for(auto point:coordinates){
            long long cur;
            cur = (long long)point[0]*n + point[1];
            s.insert(cur);
        }
        //判断包含该点的格子
        vector<long long> res(5);
        for(auto point:coordinates){
            for(int i=0;i<4;i++){
                int ox = point[0] + dir[i][0];
                int oy = point[1] + dir[i][1];
                if(ox<0||oy<0) continue;//不合法的原点坐标
                int cnt = 0;//记录当前块黑格子数目
                for(int j=0;j<4;j++){
                    long long nx = ox + next[j][0];
                    long long ny = oy + next[j][1];
                    long long cur = nx*n + ny;
                    if(s.find(cur)!=s.end()) cnt++;
                    if(nx==m||ny==n) cnt = 0;
                }
                res[cnt]++;
            }
        }
        long long rest = 0;
        for(int i=1;i<=4;i++){
            res[i] = res[i]/i;
            rest += res[i];
        }
        res[0] = (long long)(m-1)*(n-1) - rest;
        return res;
    }
};