อัลกอริทึม Flood Fill

บทนำ

กำหนด Matrix หนึ่งอัน Matrix นี้แทนหน้าจอ แต่ละอิลิเมนต์ (i, j) ของหน้าจอแทน Pixel สีของ Pixel นั้นถูกทำเครื่องหมายด้วยตัวเลขต่างๆ ในอัลกอริทึมนี้ Pixel จะถูกเติมสีใหม่เมื่อมันมีสีเดิมที่เลือก ถ้าสีไม่ใช่สีเดิม Pixel นั้นจะไม่ถูกเติม หลังจากเติม Pixel แล้ว จะตรวจสอบ Pixel ด้านบน ล่าง ซ้าย ขวา เพื่อทำอย่างเดียวกัน

แนวคิดง่ายมาก: ก่อนอื่นตรวจสอบว่าตำแหน่งที่เลือกมีสีเดิมหรือไม่ ถ้าไม่ใช่ อัลกอริทึมจะไม่ทำงาน มิฉะนั้น จะเติมสี Pixel นั้นด้วยสีใหม่ และเรียกซ้ำสำหรับเพื่อนบ้านสี่ทิศทาง

อินพุตและเอาต์พุต

Input: Matrix หน้าจอ: (ข้อมูล Matrix 8x8)
Output: Matrix หน้าจอหลัง Flood Fill (สี 2 กลายเป็นสี 3)

อัลกอริทึม

fillScreen(x, y, prevColor, newColor)
Input: พิกัด (x,y) เริ่มต้น, สีเดิม, และสีใหม่
Output: หน้าจอหลังเปลี่ยนสีจากเดิมเป็นใหม่ ถ้าเป็นไปได้

Begin
    if (x, y) ไม่ในขอบเขตหน้าจอ, then
        return
    if สีของ (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

ตัวอย่างโค้ด (C++)

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

int screen[M][N] = {
    // ขนาดหน้าจอและสี
    {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) {
    // แทนที่สีเดิมของ (x,y) ด้วยสีใหม่
    if (x < 0 || x >= M || y < 0 || y >= N)
        return;  // เมื่อจุดเกินหน้าจอ
    if (screen[x][y] != prevColor)  // ถ้าจุด (x,y) ไม่มี prevColor ไม่ทำอะไร
        return;
    screen[x][y] = newColor;  // อัปเดตสี
    fillScreen(x+1, y, prevColor, newColor);  // ขวาของ (x,y)
    fillScreen(x-1, y, prevColor, newColor);  // ซ้ายของ (x,y)
    fillScreen(x, y+1, prevColor, newColor);  // บนของ (x,y)
    fillScreen(x, y-1, prevColor, newColor);  // ล่างของ (x,y)
}

void floodFill(int x, int y, int newColor) {
    int prevColor = screen[x][y];  // เก็บสีก่อนแทนที่ด้วยสีใหม่
    fillScreen(x, y, prevColor, newColor);
}

int main() {
    int x = 4, y = 4, newColor = 3;
    cout << "Previous screen: " << endl;
    for (int i=0; i

ผลลัพธ์
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