Mô phỏng thuật toán Tô loang (flood fill)

Flood Fill · Nhóm: Đệ quy

Tô loang một vùng nối liền trên lưới bằng đệ quy DFS 4 hướng, lan từ một ô sang các ô kề cùng vùng.

Ý tưởng

Từ ô xuất phát, đệ quy sang bốn ô kề trên, dưới, trái, phải.

Ba điều kiện dừng (ca cơ sở): ra ngoài biên, gặp tường (ô không thuộc vùng), hoặc ô đã tô.

Ô hợp lệ thì đánh dấu đã tô rồi tiếp tục lan sang 4 phía; nhờ dấu đã-tô nên mỗi ô chỉ xử lý một lần.

Vì sao đúng

Điều kiện đã-tô biến DFS thành duyệt mỗi ô đúng một lần, nên chi phí tuyến tính theo số ô của lưới; đệ quy tự nhiên khớp với cấu trúc lan toả của vùng nối liền.

Mã Python

def flood_fill(grid, r, c):
    n, m = len(grid), len(grid[0])
    if r < 0 or r >= n or c < 0 or c >= m:  # out of bounds
        return
    if grid[r][c] != 1:                     # wall or already filled
        return
    grid[r][c] = 2                          # mark this cell filled
    flood_fill(grid, r - 1, c)              # up
    flood_fill(grid, r + 1, c)              # down
    flood_fill(grid, r, c - 1)              # left
    flood_fill(grid, r, c + 1)              # right

Mở trang để xem mô phỏng từng bước và xuất slide bài giảng.