Giới thiệu
Cho một ma trận; ma trận này đại diện cho một màn hình. Mỗi phần tử (i, j) của màn hình được ký hiệu là một pixel, màu của pixel đó được đánh dấu bằng các số khác nhau. Trong thuật toán này, các pixel sẽ được tô màu mới khi nó đã có màu cũ được chọn. Nếu màu trước đó không phải là màu cũ, pixel đó sẽ không được tô. Sau khi tô một pixel, nó sẽ kiểm tra các pixel lên, xuống, trái, phải để làm tương tự.
Ý tưởng thực sự đơn giản: trước tiên, ta kiểm tra xem vị trí chọn có được tô màu cũ hay không, nếu không, thuật toán sẽ không hoạt động. Ngược lại, nó sẽ tô pixel đó bằng màu mới và đệ quy cho bốn hàng xóm của nó.
Đầu vào và Đầu ra
Đầu vào: Ma trận màn hình: (8x8 matrix với các giá trị 0,1,2) Đầu ra: Ma trận màn hình sau flood fill (màu 2 thay bằng màu 3)
Thuật toán
fillScreen(x, y, prevColor, newColor)
Đầu vào: Tọa độ (x,y) để bắt đầu, màu trước, và màu mới.
Đầu ra: Màn hình sau khi đổi màu từ trước sang mới, nếu có thể.
Begin
if (x, y) không trong phạm vi màn hình, then
return
if màu của (x, y) ≠ prevColor, then
return
screen[x, y] := newColor
fillScreen(x+1, y, prevColor, newColor)
fillScreen(x-1, y, prevColor, newColor)
fillScreen(x, y+1, prevColor, newColor)
fillScreen(x, y-1, prevColor, newColor)
End
Ví dụ (C++)
#include <iostream>
#define M 8
#define N 8
using namespace std;
int screen[M][N] = {
// kích thước màn hình và màu sắc
{1, 1, 1, 1, 1, 1, 1, 1},
{1, 1, 1, 1, 1, 1, 0, 0},
{1, 0, 0, 1, 1, 0, 1, 1},
{1, 2, 2, 2, 2, 0, 1, 0},
{1, 1, 1, 2, 2, 0, 1, 0},
{1, 1, 1, 2, 2, 2, 2, 0},
{1, 1, 1, 1, 1, 2, 1, 1},
{1, 1, 1, 1, 1, 2, 2, 1}
};
void fillScreen(int x, int y, int prevColor, int newColor) {
// thay thế màu trước của (x,y) bằng màu mới
if (x < 0 || x >= M || y < 0 || y >= N)
return; // khi điểm vượt quá màn hình
if (screen[x][y] != prevColor) // nếu điểm (x,y) không chứa prevColor, không làm gì
return;
screen[x][y] = newColor; // cập nhật màu
fillScreen(x+1, y, prevColor, newColor); // cho bên phải của (x,y)
fillScreen(x-1, y, prevColor, newColor); // cho bên trái của (x,y)
fillScreen(x, y+1, prevColor, newColor); // cho phía trên của (x,y)
fillScreen(x, y-1, prevColor, newColor); // cho phía dưới của (x,y)
}
void floodFill(int x, int y, int newColor) {
int prevColor = screen[x][y]; // lấy màu trước khi thay bằng màu mới
fillScreen(x, y, prevColor, newColor);
}
int main() {
int x = 4, y = 4, newColor = 3;
cout << "Previous screen: " << endl;
for (int i=0; i<M; i++) {
for (int j=0; j<N; j++)
cout << screen[i][j] << " ";
cout << endl;
}
cout << endl;
floodFill(x, y, newColor); // bắt đầu từ (4, 4), với màu mới 3
cout << "Updated screen: " << endl;
for (int i=0; i<M; i++) {
for (int j=0; j<N; j++)
cout << screen[i][j] << " ";
cout << endl;
}
}
Kết quả
Previous screen 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0 0 1 1 0 1 1 1 2 2 2 2 0 1 0 1 1 1 2 2 0 1 0 1 1 1 2 2 2 2 0 1 1 1 1 1 2 1 1 1 1 1 1 1 2 2 1 Updated screen: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0 0 1 1 0 1 1 1 3 3 3 3 0 1 0 1 1 1 3 3 0 1 0 1 1 1 3 3 3 3 0 1 1 1 1 1 3 1 1 1 1 1 1 1 3 3 1