Chương trình tô màu vùng bằng thuật toán flood fill bằng Python

Cho lưới 2D chứa các màu "r", "g", "b". Thực hiện flood fill tại hàng r, cột c với màu target. Thay thế tất cả ô kết nối (lên/xuống/trái/phải) và có cùng màu với ô gốc bằng màu target.

Ví dụ: ma trận 3x3 toàn 'r' tại hàng 0, cột 0 tô thành 'g' → các ô 'r' liên thông đều thành 'g'.

Quy trình giải quyết (DFS)

1. Tạo tập seen lưu ô đã thăm.
2. Lưu oldcolor = matrix[r][c].
3. Định nghĩa hàm dfs(i, j):
   • Nếu ô hợp lệ, chưa thăm, và màu bằng oldcolor:
     • Đánh dấu đã thăm, đổi màu thành target.
     • Gọi đệ quy 4 hướng: (i+1,j), (i,j+1), (i,j-1), (i-1,j).
4. Gọi dfs(r, c) và trả về ma trận.

Ví dụ mã nguồn

class Solution:
    def solve(self, matrix, r, c, target):
        def dfs(i, j):
            if (0 <= i < len(matrix) and 0 <= 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, c, target = 0, 0, "g"
print(ob.solve(matrix, r, c, target))
# Output: [['g', 'g', 'g'], ['g', 'g', 'b'], ['g', 'b', 'b']]

Đầu vào

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

Đầu ra

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