find-the-grid-of-region-average.cpp

// Time:  O(m * n)
// Space: O(m * n)

// array
class Solution {
public:
    vector<vector<int>> resultGrid(vector<vector<int>>& image, int threshold) {
        const auto& check = [&](int i, int j) {
            for (int ni = i - 1; ni <= i; ++ni) {
                for (int nj = j - 1; nj <= j + 1; ++nj) {
                    if (abs(image[ni][nj] - image[ni + 1][nj]) > threshold) {
                        return false;
                    }
                }
            }
            for (int ni = i - 1; ni <= i + 1; ++ni) {
                for (int nj = j - 1; nj <= j; ++nj) {
                    if (abs(image[ni][nj] - image[ni][nj + 1]) > threshold) {
                        return false;
                    }
                }
            }
            return true;
        };
    
        vector<vector<int>> result(size(image), vector<int>(size(image[0])));
        vector<vector<int>> cnt(size(image), vector<int>(size(image[0])));
        for (int i = 1; i + 1 < size(image); ++i) {
            for (int j = 1; j + 1 < size(image[0]); ++j) {
                if (!check(i, j)) {
                    continue;
                }
                int total = 0;
                for (int ni = i - 1; ni <= i + 1; ++ni) {
                    for (int nj = j - 1; nj <= j + 1; ++nj) {
                        total += image[ni][nj];
                    }
                }
                total /= 9;
                for (int ni = i - 1; ni <= i + 1; ++ni) {
                    for (int nj = j - 1; nj <= j + 1; ++nj) {
                        ++cnt[ni][nj];
                        result[ni][nj] += total;
                    }
                }
            }
        }
        for (int i = 0; i < size(image); ++i) {
            for (int j = 0; j < size(image[0]); ++j) {
                if (cnt[i][j]) {
                    result[i][j] /= cnt[i][j];
                } else {
                    result[i][j] = image[i][j];
                }
            }
        }
        return result;
    }
};