Try All Regions with Two Extra Grids
Intuition\n Describe your first thoughts on how to solve this problem. \nWe are able to inspect each 3x3 region given the constraint is small. (500-3) * (500-3)
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nWe are able to inspect each 3x3 region given the constraint is small. (500-3) * (500-3) * 9 < 25 * 9 * 10^4 < 3 * 10^6.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nEnumerate the starting position of each region in range [0, m-3] and [0, n-3]. Check if the region is valid by checking adjacent cells. For simplicity we traverse the middle column/row for their neighbors.\n\nUse two extra grids `sum` and `cnt` to keep the sum of region average and number of regions it belongs to. In the end `sum[i][j] / cnt[i][j]` is the answer when `cnt[i][j]` is not 0. We use sum and final answer as the same grid.\n\n# Complexity\n- Time complexity: O(mn * 9) -> O(mn)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(mn)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    vector<vector<int>> resultGrid(vector<vector<int>>& image, int threshold) {\n        int m = image.size(), n = image[0].size();\n        vector<vector<int>> ans(m, vector<int>(n));\n        vector<vector<int>> cnt(m, vector<int>(n));\n        for (int i = 0; i <= m - 3; i++) {\n            for (int j = 0; j <= n - 3; j++) {\n                bool valid = true;\n                for (int p = 0; p < 3; p++) {\n                    // central vertical line with left and right\n                    if (abs(image[i+p][j] - image[i+p][j+1]) > threshold ||\n                        abs(image[i+p][j+1] - image[i+p][j+2]) > threshold) {\n                        valid = false;\n                        break;\n                    }\n\n                    // central horizontal line with up and down\n                    if (abs(image[i+1][j+p] - image[i][j+p]) > threshold ||\n                        abs(image[i+1][j+p] - image[i+2][j+p]) > threshold) {\n                        valid = false;\n                        break;\n                    }\n                }\n                \n                if (valid) {\n                    int sum = 0;\n                    for (int p = 0; p < 3; p++) {\n                        for (int q = 0; q < 3; q++) {\n                            sum += image[i+p][j+q];\n                        }\n                    }\n                    \n                    for (int p = 0; p < 3; p++) {\n                        for (int q = 0; q < 3; q++) {\n                            ans[i+p][j+q] += sum / 9;\n                            cnt[i+p][j+q]++;\n                        }\n                    }\n                }\n            }\n        }\n        \n        for (int i = 0; i < m; i++) {\n            for (int j = 0; j < n; j++) {\n                ans[i][j] = cnt[i][j] > 0 ? (ans[i][j] / cnt[i][j]) : image[i][j];\n            }\n        }\n        \n        return ans;\n    }\n};\n```
['C++']