<p>You are given <code>m x n</code> grid <code>image</code> which represents a grayscale image, where <code>image[i][j]</code> represents a pixel with intensity in the range <code>[0..255]</code>. You are also given a <strong>non-negative</strong> integer <code>threshold</code>.</p>

<p>Two pixels are <strong>adjacent</strong> if they share an edge.</p>

<p>A <strong>region</strong> is a <code>3 x 3</code> subgrid where the <strong>absolute difference</strong> in intensity between any two <strong>adjacent</strong> pixels is <strong>less than or equal to</strong> <code>threshold</code>.</p>

<p>All pixels in a region belong to that region, note that a pixel can belong to <strong>multiple</strong> regions.</p>

<p>You need to calculate a <code>m x n</code> grid <code>result</code>, where <code>result[i][j]</code> is the <strong>average</strong> intensity of the regions to which <code>image[i][j]</code> belongs, <strong>rounded down</strong> to the nearest integer. If <code>image[i][j]</code> belongs to multiple regions, <code>result[i][j]</code> is the <strong>average </strong>of the<strong> rounded-down average </strong>intensities of these regions, <strong>rounded down</strong> to the nearest integer. If <code>image[i][j]</code> does<strong> not</strong> belong to any region, <code>result[i][j]</code> is <strong>equal to</strong> <code>image[i][j]</code>.</p>

<p>Return the grid <code>result</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">image = [[5,6,7,10],[8,9,10,10],[11,12,13,10]], threshold = 3</span></p>

<p><strong>Output:</strong> <span class="example-io">[[9,9,9,9],[9,9,9,9],[9,9,9,9]]</span></p>

<p><strong>Explanation:</strong></p>

<p><img alt="" src="https://assets.leetcode.com/uploads/2023/12/21/example0corrected.png" style="width: 832px; height: 275px;" /></p>

<p>There are two regions as illustrated above. The average intensity of the first region is 9, while the average intensity of the second region is 9.67 which is rounded down to 9. The average intensity of both of the regions is (9 + 9) / 2 = 9. As all the pixels belong to either region 1, region 2, or both of them, the intensity of every pixel in the result is 9.</p>

<p>Please note that the rounded-down values are used when calculating the average of multiple regions, hence the calculation is done using 9 as the average intensity of region 2, not 9.67.</p>
</div>

<p><strong class="example">Example 2:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">image = [[10,20,30],[15,25,35],[20,30,40],[25,35,45]], threshold = 12</span></p>

<p><strong>Output:</strong> <span class="example-io">[[25,25,25],[27,27,27],[27,27,27],[30,30,30]]</span></p>

<p><strong>Explanation:</strong></p>

<p><img src="https://assets.leetcode.com/uploads/2023/12/21/example1corrected.png" /></p>

<p>There are two regions as illustrated above. The average intensity of the first region is 25, while the average intensity of the second region is 30. The average intensity of both of the regions is (25 + 30) / 2 = 27.5 which is rounded down to 27.</p>

<p>All the pixels in row 0 of the image belong to region 1, hence all the pixels in row 0 in the result are 25. Similarly, all the pixels in row 3 in the result are 30. The pixels in rows 1 and 2 of the image belong to region 1 and region 2, hence their assigned value is 27 in the result.</p>
</div>

<p><strong class="example">Example 3:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">image = [[5,6,7],[8,9,10],[11,12,13]], threshold = 1</span></p>

<p><strong>Output:</strong> <span class="example-io">[[5,6,7],[8,9,10],[11,12,13]]</span></p>

<p><strong>Explanation:</strong></p>

<p>There is only one <code>3 x 3</code> subgrid, while it does not have the condition on difference of adjacent pixels, for example, the difference between <code>image[0][0]</code> and <code>image[1][0]</code> is <code>|5 - 8| = 3 &gt; threshold = 1</code>. None of them belong to any valid regions, so the <code>result</code> should be the same as <code>image</code>.</p>
</div>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>3 &lt;= n, m &lt;= 500</code></li>
	<li><code>0 &lt;= image[i][j] &lt;= 255</code></li>
	<li><code>0 &lt;= threshold &lt;= 255</code></li>
</ul>

class Solution:
    def resultGrid(self, image: List[List[int]], threshold: int) -> List[List[int]]:
        m, n = len(image), len(image[0])
        
        # 初始化结果网格和每个像素的区域平均强度列表
        result = [[0] * n for _ in range(m)]
        averages_list = [[[] for _ in range(n)] for _ in range(m)]
        
        # 获取区域内所有位置和相邻像素对
        positions_in_region = self.get_positions_in_region()
        adjacent_offsets = self.get_adjacent_offsets()
        
        # 遍历所有可能的3x3区域
        for i in range(m - 2):
            for j in range(n - 2):
                # 检查区域是否有效
                if self.is_valid_region(image, i, j, threshold, adjacent_offsets):
                    # 计算区域的平均强度
                    region_avg = self.calculate_region_average(image, i, j, positions_in_region)
                    # 将区域平均强度添加到该区域内每个像素的列表中
                    for dx, dy in positions_in_region:
                        x, y = i + dx, j + dy
                        averages_list[x][y].append(region_avg)
        
        # 计算每个像素的结果值
        for i in range(m):
            for j in range(n):
                if not averages_list[i][j]:
                    result[i][j] = image[i][j]
                else:
                    # 计算所属区域的平均强度的平均值（向下取整）
                    pixel_avg = sum(averages_list[i][j]) // len(averages_list[i][j])
                    result[i][j] = pixel_avg
        
        return result

    def get_positions_in_region(self):
        """
        获取3x3区域内的所有相对位置。
        """
        return [(dx, dy) for dx in range(3) for dy in range(3)]
    
    def get_adjacent_offsets(self):
        """
        获取3x3区域内所有相邻像素对的相对位置偏移。
        """
        adjacent_offsets = []
        for dx in range(3):
            for dy in range(3):
                if dx < 2:
                    adjacent_offsets.append(((dx, dy), (dx + 1, dy)))  # 水平相邻像素
                if dy < 2:
                    adjacent_offsets.append(((dx, dy), (dx, dy + 1)))  # 垂直相邻像素
        return adjacent_offsets
    
    def is_valid_region(self, image, i, j, threshold, adjacent_offsets):
        """
        检查以(i, j)为左上角的3x3区域是否有效。
        """
        # 遍历区域内所有相邻像素对
        for (pos1, pos2) in adjacent_offsets:
            x1, y1 = i + pos1[0], j + pos1[1]
            x2, y2 = i + pos2[0], j + pos2[1]
            # 计算相邻像素的强度差
            diff = abs(image[x1][y1] - image[x2][y2])
            if diff > threshold:
                return False  # 如果任何相邻像素对的差值超过阈值，区域无效
        return True  # 所有相邻像素对的差值都不超过阈值，区域有效
    
    def calculate_region_average(self, image, i, j, positions_in_region):
        """
        计算以(i, j)为左上角的3x3区域的平均强度。
        """
        region_sum = 0
        # 累加区域内所有像素的强度值
        for dx, dy in positions_in_region:
            x, y = i + dx, j + dy
            region_sum += image[x][y]
        # 计算区域的平均强度（向下取整）
        region_avg = region_sum // 9
        return region_avg

4106