Thuật toán Flood Fill (tô màu) trong C++

Mô tả bài toán

Cho màn hình 2D (mảng ký tự), tọa độ pixel (x,y) và màu mới. Tô màu pixel đó và tất cả pixel liền kề (4 hướng) cùng màu cũ bằng màu mới.

Ví dụ

Màn hình 8x8, tô tại (5,5) màu 'R' → các vùng 'Y' liên thông được tô thành 'R'.

Giải thuật (Đệ quy DFS)

1. Lưu màu cũ = screen[x][y]. Nếu trùng màu mới → return.
2. Đệ quy: nếu tọa độ hợp lệ, màu = màu cũ, chưa phải màu mới → gán màu mới, gọi đệ quy 4 hướng (trên, dưới, trái, phải).

Mã nguồn C++

#include <iostream>
using namespace std;
#define M 8
#define N 8

void fillColorAdj(char scr[][N], int x, int y, char oldC, char newC) {
    if (x<0 || x>=M || y<0 || y>=N) return;
    if (scr[x][y] != oldC) return;
    if (scr[x][y] == newC) return;
    scr[x][y] = newC;
    fillColorAdj(scr, x+1, y, oldC, newC);
    fillColorAdj(scr, x-1, y, oldC, newC);
    fillColorAdj(scr, x, y+1, oldC, newC);
    fillColorAdj(scr, x, y-1, oldC, newC);
}

void fillColor(char scr[][N], int x, int y, char newC) {
    char oldC = scr[x][y];
    if (oldC == newC) return;
    fillColorAdj(scr, x, y, oldC, newC);
}

int main() {
    char screen[M][N] = {
        {'W','W','B','W','W','W','W','W'},
        {'W','W','W','W','W','W','B','B'},
        {'W','B','B','W','W','B','W','W'},
        {'W','Y','Y','Y','Y','B','W','B'},
        {'B','W','W','Y','Y','B','W','B'},
        {'B','W','W','Y','Y','Y','Y','B'},
        {'W','B','W','W','W','Y','W','W'},
        {'W','W','B','B','W','Y','Y','W'}
    };
    fillColor(screen, 5, 5, 'R');
    for (int i=0;i

Màn hình sau tô màu (R thay thế Y trong vùng liên thông từ (5,5))