为了方便，我们称每个单元格及其八连通方向单元格所组成的连通块为一个 item。

数据范围只有

，我们可以直接对每个 item 进行遍历模拟。

Java 代码：

class Solution {    public int[][] imageSmoother(int[][] img) {        int m = img.length, n = img[0].length;        int[][] ans = new int[m][n];        int[][] dirs = new int[][]{{0,0},{1,0},{-1,0},{0,1},{0,-1},{-1,-1},{-1,1},{1,-1},{1,1}};        for (int i = 0; i = m || ny = n) continue;                    tot += img[nx][ny]; cnt++;                }                ans[i][j] = tot / cnt;            }        }        return ans;    }}

C++ 代码：

class Solution {public:    vector> imageSmoother(vector>& img) {        int m = img.size();        if (m == 0) return {};        int n = img[0].size();        vector> ans(m, vector(n, 0));        vector> dirs = {{0, 0}, {1, 0}, {-1, 0}, {0, 1}, {0, -1}, {-1, -1}, {-1, 1}, {1, -1}, {1, 1}};        for (int i = 0; i = m || ny = n) continue;                    tot += img[nx][ny]; cnt++;                }                ans[i][j] = tot / cnt;            }        }        return ans;    }};

Python 代码：

dirs = list(product(*[[-1,0,1]] * 2))class Solution:    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:        m, n = len(img), len(img[0])        ans = [[0] * n for _ in range(m)]        for i in range(m):            for j in range(n):                tot, cnt = 0, 0                for di in dirs:                    if 0 
TypeScript 代码：
代码语言：javascript代码运行次数：0运行复制
function imageSmoother(img: number[][]): number[][] {    const m = img.length;    if (m === 0) return [];    const n = img[0].length;    const ans = new Array(m).fill(0).map(() => new Array(n).fill(0));    const dirs = [[0, 0], [1, 0], [-1, 0], [0, 1], [0, -1], [-1, -1], [-1, 1], [1, -1], [1, 1]];    for (let i = 0; i = m || ny = n) continue;                tot += img[nx][ny]; cnt++;            }            ans[i][j] = Math.floor(tot / cnt);        }    }    return ans;};
登录后复制时间复杂度：
O(m 	imes n 	imes C)
，其中 
C
 为灰度单位所包含的单元格数量，固定为 
9
空间复杂度：
O(m 	imes n)
前缀和
在朴素解法中，对于每个 
ans[i][j]
 我们都不可避免的遍历 
8
 联通方向，而利用「前缀和」我们可以对该操作进行优化。
对于某个 
ans[i][j]
 而言，我们可以直接计算出其所在 item 的左上角 
(a, b) = (i - 1, j - 1)
 以及其右下角 
(c, d) = (i + 1, j + 1)
，同时为了防止超出原矩阵，我们需要将 
(a, b)
 与 
(c, d)
 对边界分别取 max 和 min。
当有了合法的 
(a, b)
 和 
(c, d)
 后，我们可以直接计算出 item 的单元格数量（所包含的行列乘积）及 item  的单元格之和（前缀和查询），从而算得 
ans[i][j]
。
Java 代码：
代码语言：javascript代码运行次数：0运行复制
class Solution {    public int[][] imageSmoother(int[][] img) {        int m = img.length, n = img[0].length;        int[][] sum = new int[m + 10][n + 10];        for (int i = 1; i 
C++ 代码：
代码语言：javascript代码运行次数：0运行复制
class Solution {public:    vector> imageSmoother(vector>& img) {        int m = img.size(), n = img[0].size();        vector> sumv(m + 2, vector(n + 2, 0));        for (int i = 1; i > ans(m, vector(n, 0));        for (int i = 0; i 
Python 代码：
代码语言：javascript代码运行次数：0运行复制
class Solution:    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:        m, n = len(img), len(img[0])        sum = [[0] * (n + 10) for _ in range(m + 10)]        for i in range(1, m + 1):            for j in range(1, n + 1):                sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + img[i - 1][j - 1]        ans = [[0] * n for _ in range(m)]        for i in range(m):            for j in range(n):                a, b = max(0, i - 1), max(0, j - 1)                c, d = min(m - 1, i + 1), min(n - 1, j + 1)                cnt = (c - a + 1) * (d - b + 1)                tot = sum[c + 1][d + 1] - sum[a][d + 1] - sum[c + 1][b] + sum[a][b]                ans[i][j] = tot // cnt        return ans
登录后复制
TypeScript 代码：
代码语言：javascript代码运行次数：0运行复制
function imageSmoother(img: number[][]): number[][] {    const m = img.length, n = img[0].length;    const sum = Array.from({ length: m + 10 }, () => new Array(n + 10).fill(0));    for (let i = 1; i  new Array(n).fill(0));    for (let i = 0; i 时间复杂度：
O(m 	imes n)
空间复杂度：
O(m 	imes n)
登录后复制