Brute-Force + O(1) Memory Bonus
Check all 3x3 subgrids. If it is a region, store the average in each region\'s cell.\n    \nNote that we need to store multiple (up to 9) averages for each cell
Check all 3x3 subgrids. If it is a region, store the average in each region\'s cell.\n    \nNote that we need to store multiple (up to 9) averages for each cell.  \n\n> Per the optimization suggested by [Darrenyang](https://leetcode.com/Darrenyang/), we can just track the sum of averages, and the number of regions.\n  \n> Also, check out the second solution below that does not require any additional memory.\n\nThat way, we can compute the average of averages in the end.\n\n**C++**\n```cpp\nvector<vector<int>> resultGrid(vector<vector<int>>& img, int threshold) {\n    int n = img.size(), m = img[0].size(), reg[501][501][2] = {};\n    for (int i = 0; i < n - 2; ++i)\n        for (int j = 0; j < m - 2; ++j) {\n            int sum = 0, is_region = true;\n            for (int k = i; k < i + 3; ++k)\n                for (int l = j; l < j + 3; ++l) {\n                    sum += img[k][l];\n                    is_region &= k == i || abs(img[k][l] - img[k - 1][l]) <= threshold;\n                    is_region &= l == j || abs(img[k][l] - img[k][l - 1]) <= threshold;\n                }\n            if (is_region)\n                for (int k = i; k < i + 3; ++k)\n                    for (int l = j; l < j + 3; ++l) {\n                        reg[k][l][0] += sum / 9;\n                        reg[k][l][1] += 1;\n                    }\n        }\n    for (int i = 0; i < n; ++i)\n        for (int j = 0; j < m; ++j)\n            if (reg[i][j][1])\n                img[i][j] = reg[i][j][0] / reg[i][j][1];\n    return img;\n}\n```\n\n## O(1) Memory\nHere, we leverage the fact that cell value, and thus the average, is limited to `255`, and the sum of all region averages is limited to `9 * 255`.\n\nWe can store the information to compute region averages in the existing cell:\n- Bits 0-7: intensity (original value) [0..255]\n- Bits 8-11: number of regions [0..9]\n- Bits 12+: sum of averages, [0...9 * 255]\n\n**C++**\n```cpp\nvector<vector<int>> resultGrid(vector<vector<int>>& img, int threshold) {\n    int n = img.size(), m = img[0].size();\n    for (int i = 0; i < n - 2; ++i)\n        for (int j = 0; j < m - 2; ++j) {\n            int sum = 0, is_region = true;\n            for (int k = i; k < i + 3; ++k)\n                for (int l = j; l < j + 3; ++l) {\n                    sum += (img[k][l] & 255);\n                    is_region &= k == i || abs((img[k][l] & 255) - (img[k - 1][l] & 255)) <= threshold;\n                    is_region &= l == j || abs((img[k][l] & 255) - (img[k][l - 1] & 255)) <= threshold;\n                }\n            if (is_region)\n                for (int k = i; k < i + 3; ++k)\n                    for (int l = j; l < j + 3; ++l) {\n                        img[k][l] += (sum / 9) << 12;\n                        img[k][l] += 1 << 8;\n                    }\n        }\n    for (int i = 0; i < n; ++i)\n        for (int j = 0; j < m; ++j)\n            if (img[i][j] >> 8)\n                img[i][j] = (img[i][j] >> 12) / ((img[i][j] >> 8) & 15);\n    return img;\n}\n```
[]