โปรแกรมเติมสีโดยใช้การเติมน้ำท่วมใน Python

สมมติว่าเรามีตาราง 2D ที่มีสีเป็นสตริง "r", "g" และ "b" เราต้องดำเนินการเติมน้ำท่วมที่แถว r คอลัมน์ c โดยมีเป้าหมายสี ดังที่เราทราบแล้วว่าการดำเนินการเติมน้ำท่วมควรแทนที่องค์ประกอบทั้งหมดที่เชื่อมต่อกับ grid[r,c] (ขึ้น/ขวา/ลง/ซ้าย) และมีสีเดียวกับ grid[r,c] ด้วยสีเดียวกันกับเป้าหมาย

ดังนั้นหากอินพุตเป็นแบบ

แล้วผลลัพธ์ที่ได้จะเป็น

เนื่องจากเซลล์สีแดงที่เชื่อมต่อกับกริด[0,0] จะถูกแทนที่ด้วยสีเขียว ("g")

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดชุดใหม่ที่เห็น
• สีเก่า :=matrix[r, c]
• กำหนดฟังก์ชัน dfs() นี่จะใช้เวลา i, j
• ถ้า i และ j อยู่ในเมทริกซ์และ (i, j) ไม่เห็นและเมทริกซ์[i, j] จะเหมือนกับสีเก่า ดังนั้น
  • เพิ่ม (i, j) ที่เห็น
  • เมทริกซ์[i, j] :=เป้าหมาย
  • dfs(i + 1, j)
  • dfs(i, j + 1)
  • dfs(i, j - 1)
  • dfs(i - 1, j
• จากวิธีหลัก ให้ทำดังต่อไปนี้ −
• dfs(r, c)
• เมทริกซ์ผลตอบแทน

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

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']]