Flood fill บนกริด 2 มิติ: ให้กริดสี 'r','g','b' เริ่มที่ (r,c) เปลี่ยนสีพื้นที่ที่เชื่อมต่อ (4 ทิศทาง) และมีสีเดิมเดียวกัน ให้เป็นสี target
ตัวอย่าง: เริ่ม (0,0) สี 'r' เปลี่ยนเป็น 'g' → ทุก 'r' ที่ติดกันกลายเป็น 'g'
อัลกอริธึม DFS Recursive
- เก็บ
oldcolor= สีที่ตำแหน่งเริ่มต้น - DFS จาก (r,c): ถ้าอยู่ในกริด ยังไม่เยี่ยม และสีเท่า
oldcolor→ เปลี่ยนเป็น target เรียก DFS 4 ทิศทาง
การนำไปใช้
class Solution:
def solve(self, matrix, r, c, target):
seen = set()
oldcolor = matrix[r][c]
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)
dfs(r, c)
return matrix
ob = Solution()
matrix = [["r","r","r"], ["r","g","b"], ["g","b","b"]]
print(ob.solve(matrix, 0, 0, "g"))
# [['g','g','g'], ['g','g','b'], ['g','b','b']]
