Question

3030. 找出网格的区域平均强度

English Version

题目描述

给你一个下标从 0 开始、大小为 m x n 的网格 image ，表示一个灰度图像，其中 image[i][j] 表示在范围 [0..255] 内的某个像素强度。另给你一个 非负 整数 threshold 。

如果 image[a][b] 和 image[c][d] 满足 |a - c| + |b - d| == 1 ，则称这两个像素是 相邻像素 。

区域 是一个 3 x 3 的子网格，且满足区域中任意两个 相邻 像素之间，像素强度的 绝对差 小于或等于 threshold 。

区域 内的所有像素都认为属于该区域，而一个像素 可以 属于 多个 区域。

你需要计算一个下标从 0 开始、大小为 m x n 的网格 result ，其中 result[i][j] 是 image[i][j] 所属区域的 平均 强度，向下取整 到最接近的整数。如果 image[i][j] 属于多个区域，result[i][j] 是这些区域的 “取整后的平均强度” 的 平均值，也 向下取整 到最接近的整数。如果 image[i][j] 不属于任何区域，则 result[i][j] 等于 image[i][j] 。

返回网格 result 。

 

示例 1：

输入：image = [[5,6,7,10],[8,9,10,10],[11,12,13,10]], threshold = 3
输出：[[9,9,9,9],[9,9,9,9],[9,9,9,9]]
解释：图像中存在两个区域，如图片中的阴影区域所示。第一个区域的平均强度为 9 ，而第二个区域的平均强度为 9.67 ，向下取整为 9 。两个区域的平均强度为 (9 + 9) / 2 = 9 。由于所有像素都属于区域 1 、区域 2 或两者，因此 result 中每个像素的强度都为 9 。
注意，在计算多个区域的平均值时使用了向下取整的值，因此使用区域 2 的平均强度 9 来进行计算，而不是 9.67 。

示例 2：

输入：image = [[10,20,30],[15,25,35],[20,30,40],[25,35,45]], threshold = 12
输出：[[25,25,25],[27,27,27],[27,27,27],[30,30,30]]
解释：图像中存在两个区域，如图片中的阴影区域所示。第一个区域的平均强度为 25 ，而第二个区域的平均强度为 30 。两个区域的平均强度为 (25 + 30) / 2 = 27.5 ，向下取整为 27 。图像中第 0 行的所有像素属于区域 1 ，因此 result 中第 0 行的所有像素为 25 。同理，result 中第 3 行的所有像素为 30 。图像中第 1 行和第 2 行的像素属于区域 1 和区域 2 ，因此它们在 result 中的值为 27 。

示例 3：

输入：image = [[5,6,7],[8,9,10],[11,12,13]], threshold = 1
输出：[[5,6,7],[8,9,10],[11,12,13]]
解释：图像中不存在任何区域，因此对于所有像素，result[i][j] == image[i][j] 。

 

提示：

• 3 <= n, m <= 500
• 0 <= image[i][j] <= 255
• 0 <= threshold <= 255

解法

方法一

class Solution:
  def resultGrid(self, image: List[List[int]], threshold: int) -> List[List[int]]:
    n, m = len(image), len(image[0])
    ans = [[0] * m for _ in range(n)]
    ct = [[0] * m for _ in range(n)]
    for i in range(n - 2):
      for j in range(m - 2):
        region = True
        for k in range(3):
          for l in range(2):
            region &= (
              abs(image[i + k][j + l] - image[i + k][j + l + 1])
              <= threshold
            )
        for k in range(2):
          for l in range(3):
            region &= (
              abs(image[i + k][j + l] - image[i + k + 1][j + l])
              <= threshold
            )

        if region:
          tot = 0
          for k in range(3):
            for l in range(3):
              tot += image[i + k][j + l]
          for k in range(3):
            for l in range(3):
              ct[i + k][j + l] += 1
              ans[i + k][j + l] += tot // 9

    for i in range(n):
      for j in range(m):
        if ct[i][j] == 0:
          ans[i][j] = image[i][j]
        else:
          ans[i][j] //= ct[i][j]

    return ans

class Solution {
  public int[][] resultGrid(int[][] image, int threshold) {
    int n = image.length;
    int m = image[0].length;
    int[][] ans = new int[n][m];
    int[][] ct = new int[n][m];
    for (int i = 0; i + 2 < n; ++i) {
      for (int j = 0; j + 2 < m; ++j) {
        boolean region = true;
        for (int k = 0; k < 3; ++k) {
          for (int l = 0; l < 2; ++l) {
            region
              &= Math.abs(image[i + k][j + l] - image[i + k][j + l + 1]) <= threshold;
          }
        }
        for (int k = 0; k < 2; ++k) {
          for (int l = 0; l < 3; ++l) {
            region
              &= Math.abs(image[i + k][j + l] - image[i + k + 1][j + l]) <= threshold;
          }
        }
        if (region) {
          int tot = 0;
          for (int k = 0; k < 3; ++k) {
            for (int l = 0; l < 3; ++l) {
              tot += image[i + k][j + l];
            }
          }
          for (int k = 0; k < 3; ++k) {
            for (int l = 0; l < 3; ++l) {
              ct[i + k][j + l]++;
              ans[i + k][j + l] += tot / 9;
            }
          }
        }
      }
    }
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < m; ++j) {
        if (ct[i][j] == 0) {
          ans[i][j] = image[i][j];
        } else {
          ans[i][j] /= ct[i][j];
        }
      }
    }
    return ans;
  }
}

class Solution {
public:
  vector<vector<int>> resultGrid(vector<vector<int>>& image, int threshold) {
    int n = image.size(), m = image[0].size();
    vector<vector<int>> ans(n, vector<int>(m));
    vector<vector<int>> ct(n, vector<int>(m));
    for (int i = 0; i + 2 < n; ++i) {
      for (int j = 0; j + 2 < m; ++j) {
        bool region = true;
        for (int k = 0; k < 3; ++k) {
          for (int l = 0; l < 2; ++l) {
            region &= abs(image[i + k][j + l] - image[i + k][j + l + 1]) <= threshold;
          }
        }
        for (int k = 0; k < 2; ++k) {
          for (int l = 0; l < 3; ++l) {
            region &= abs(image[i + k][j + l] - image[i + k + 1][j + l]) <= threshold;
          }
        }
        if (region) {
          int tot = 0;
          for (int k = 0; k < 3; ++k) {
            for (int l = 0; l < 3; ++l) {
              tot += image[i + k][j + l];
            }
          }
          for (int k = 0; k < 3; ++k) {
            for (int l = 0; l < 3; ++l) {
              ct[i + k][j + l]++;
              ans[i + k][j + l] += tot / 9;
            }
          }
        }
      }
    }
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < m; ++j) {
        if (ct[i][j] == 0) {
          ans[i][j] = image[i][j];
        } else {
          ans[i][j] /= ct[i][j];
        }
      }
    }
    return ans;
  }
};

func resultGrid(image [][]int, threshold int) [][]int {
  n := len(image)
  m := len(image[0])
  ans := make([][]int, n)
  ct := make([][]int, n)
  for i := range ans {
    ans[i] = make([]int, m)
    ct[i] = make([]int, m)
  }
  for i := 0; i+2 < n; i++ {
    for j := 0; j+2 < m; j++ {
      region := true
      for k := 0; k < 3; k++ {
        for l := 0; l < 2; l++ {
          region = region && abs(image[i+k][j+l]-image[i+k][j+l+1]) <= threshold
        }
      }
      for k := 0; k < 2; k++ {
        for l := 0; l < 3; l++ {
          region = region && abs(image[i+k][j+l]-image[i+k+1][j+l]) <= threshold
        }
      }
      if region {
        tot := 0
        for k := 0; k < 3; k++ {
          for l := 0; l < 3; l++ {
            tot += image[i+k][j+l]
          }
        }
        for k := 0; k < 3; k++ {
          for l := 0; l < 3; l++ {
            ct[i+k][j+l]++
            ans[i+k][j+l] += tot / 9
          }
        }
      }
    }
  }
  for i := 0; i < n; i++ {
    for j := 0; j < m; j++ {
      if ct[i][j] == 0 {
        ans[i][j] = image[i][j]
      } else {
        ans[i][j] /= ct[i][j]
      }
    }
  }
  return ans
}
func abs(x int) int {
  if x < 0 {
    return -x
  }
  return x
}

function resultGrid(image: number[][], threshold: number): number[][] {
  const n: number = image.length;
  const m: number = image[0].length;
  const ans: number[][] = new Array(n).fill(0).map(() => new Array(m).fill(0));
  const ct: number[][] = new Array(n).fill(0).map(() => new Array(m).fill(0));
  for (let i = 0; i + 2 < n; ++i) {
    for (let j = 0; j + 2 < m; ++j) {
      let region: boolean = true;
      for (let k = 0; k < 3; ++k) {
        for (let l = 0; l < 2; ++l) {
          region &&= Math.abs(image[i + k][j + l] - image[i + k][j + l + 1]) <= threshold;
        }
      }
      for (let k = 0; k < 2; ++k) {
        for (let l = 0; l < 3; ++l) {
          region &&= Math.abs(image[i + k][j + l] - image[i + k + 1][j + l]) <= threshold;
        }
      }
      if (region) {
        let tot: number = 0;

        for (let k = 0; k < 3; ++k) {
          for (let l = 0; l < 3; ++l) {
            tot += image[i + k][j + l];
          }
        }
        for (let k = 0; k < 3; ++k) {
          for (let l = 0; l < 3; ++l) {
            ct[i + k][j + l]++;
            ans[i + k][j + l] += Math.floor(tot / 9);
          }
        }
      }
    }
  }
  for (let i = 0; i < n; ++i) {
    for (let j = 0; j < m; ++j) {
      if (ct[i][j] === 0) {
        ans[i][j] = image[i][j];
      } else {
        ans[i][j] = Math.floor(ans[i][j] / ct[i][j]);
      }
    }
  }
  return ans;
}