Python中使用泛洪填充操作填充颜色的程序

假设我们有一个二维网格，其中包含颜色字符串“r”、“g”和“b”。我们必须在行r、列c处使用颜色target执行泛洪填充操作。众所周知，泛洪填充操作应将与grid[r,c]连接（上/右/下/左）且颜色与grid[r,c]相同的元素替换为与target相同的颜色。

因此，如果输入如下所示：

RRR
RGB
GBB

那么输出将是

GGG
GGB
GBB

因为与grid[0,0]连接的红色单元格被替换为绿色（“g”）。

为了解决这个问题，我们将遵循以下步骤：

  • 定义一个新的集合seen
  • oldcolor := matrix[r, c]
  • 定义一个函数dfs()。这将需要i, j
  • 如果i和j在矩阵中，并且(i, j)未被seen，并且matrix[i, j]与oldcolor相同，则
    • 将(i, j)添加到seen
    • matrix[i, j] := target
    • dfs(i + 1, j)
    • dfs(i, j + 1)
    • dfs(i, j - 1)
    • dfs(i - 1, j)
  • 在主方法中，执行以下操作：
  • dfs(r, c)
  • return matrix

让我们看看下面的实现，以便更好地理解：

示例

　在线演示

class Solution:
   def solve(self, matrix, r, c, target):
      def dfs(i, j):
         if (
            i >= 0
            and i < len(matrix)
            and j >= 0
            and j < len(matrix[0])
            and (i, j) not in seen
            and matrix[i][j] == oldcolor
         ):
            seen.add((i, j))
            matrix[i][j] = target
            dfs(i + 1, j)
            dfs(i, j + 1)
            dfs(i, j - 1)
            dfs(i - 1, j)
      seen = set()
      oldcolor = matrix[r][c]
      dfs(r, c)
      return matrix
ob = Solution()
matrix = [ ["r", "r", "r"], ["r", "g", "b"], ["g", "b", "b"] ]
r = 0
c = 0
target = "g"
print(ob.solve(matrix, r, c, target))

输入

matrix = [
["r", "r", "r"],
["r", "g", "b"],
["g", "b", "b"] ]
r = 0
c = 0
target = "g"

输出

[ ['g', 'g', 'g'], ['g', 'g', 'b'], ['g', 'b', 'b']]

更新于：2020年10月20日

220 次浏览

启动您的职业生涯

通过完成课程获得认证

开始学习
广告