โปรแกรมเติมสีด้วยอัลกอริทึม Flood Fill ใน Python

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

ตัวอย่าง: กริดต้นฉบับ

ขั้นตอนการแก้ปัญหา (DFS)

1. สร้างเซต seen ว่าง
2. oldcolor = matrix[r][c]
3. ฟังก์ชัน 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)
4. จากเมธอดหลัก เรียก dfs(r, c) แล้วคืนค่า matrix

ตัวอย่างโค้ด Python

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))
# Output: [['g', 'g', 'g'], ['g', 'g', 'b'], ['g', 'b', 'b']]

อินพุต / เอาต์พุต

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

Output: [['g', 'g', 'g'], ['g', 'g', 'b'], ['g', 'b', 'b']]