Cho trước một ma trận; ma trận đạ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 sắc 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ô bằng màu mới khi nó đã có màu trước đó được chọn. Nếu màu trước đó không phải là màu trước đó, pixel đó sẽ không được tô. Sau khi điền vào một pixel, nó sẽ kiểm tra các pixel lên, xuống, trái và phải của nó để thực hiện tương tự.
Ý tưởng thực sự đơn giản, đầu tiên, chúng ta kiểm tra xem vị trí đã chọn có được tô màu với màu trước đó hay không, nếu không, thuật toán sẽ không hoạt động. Nếu không, nó sẽ lấp đầy pixel đó bằng màu mới và lặp lại cho bốn vùng lân cận của nó.
Đầu vào và Đầu ra
Input: The screen matrix: 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 Output: Screen matrix after flood fill 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
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 thay đổi màu từ cũ sang mới, nếu có thể.
Begin if (x, y) not in the screen range, then return if color of (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ụ
#include<iostream>
#define M 8
#define N 8
using namespace std;
int screen[M][N] = { //the screen dimention and colors
{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) { //replace previous color of (x,y), with new color
if (x < 0 || x >= M || y < 0 || y >= N) //when point exceeds the screen
return;
if (screen[x][y] != prevColor) //if the point(x,y) are not containing prevColor, do nothing
return;
screen[x][y] = newColor; //update the color
fillScreen(x+1, y, prevColor, newColor); //for the right of (x,y)
fillScreen(x-1, y, prevColor, newColor); //for the left of (x,y)
fillScreen(x, y+1, prevColor, newColor); //for the top of (x,y)
fillScreen(x, y-1, prevColor, newColor); //for the bottom of (x,y)
}
void floodFill(int x, int y, int newColor) {
int prevColor = screen[x][y]; //take the color before replacing with new color
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); //start from (4, 4), with new color 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;
}
} Đầu ra
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