home

หน้าแรก
 Computer >> บทช่วยสอนคอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

อัลกอริทึม Flood Fill – การทำงานของ fill() ในโปรแกรมวาดรูป (C++)

ในปัญหานี้ กำหนดให้มีอาร์เรย์ 2 มิติ แทนหน้าจอ 2D พร้อมพิกัดพิกเซลที่ต้องการเติมสี และสีใหม่ ภารกิจคือสร้างโปรแกรม เติมสีพิกเซลปัจจุบันและพิกเซลติดกันทั้งหมดที่มีสีเดิมเหมือนกัน

การทำงานในโปรแกรมวาดรูป: เราเลือกสีและคลิกที่พิกเซลที่ต้องการด้วยแปรง

ตัวอย่าง

Input: Screen[][] = {{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}};
X = 5, Y = 5, newColor = R.

Output: {{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, R, R, R, R, B, W, B}, 
         {B, W, W, R, R, B, W, B}, 
         {B, W, W, R, R, R, R, B}, 
         {W, B, W, W, W, R, W, W}, 
         {W, W, B, B, W, R, R, W}};

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

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

วิธีการแก้ปัญหา (Recursive Approach)

  1. หาพิกเซลแรกที่ต้องการเติมสี
  2. ตรวจสอบพิกเซลติดกัน 4 ทิศทาง
  3. ถ้าสีเหมือนเดิม ให้เติมสีใหม่และเรียกฟังก์ชันซ้ำ (recursive) กับพิกเซลนั้น
  4. ถ้าสีต่างกัน ให้ข้ามไป
  5. ทำซ้ำจนครบทุกพิกเซลติดกันที่มีสีเดิม

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

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

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

void fillColor(char screen[][N], int x, int y, char color) {
    char oldColor = screen[x][y];
    if (oldColor == color) return;
    fillColorAdj(screen, x, y, oldColor, color);
}

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'}
    };
    
    int x = 5, y = 5;
    char color = 'R';
    
    cout << "The initial screen coordinates are : \n";
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++)
            cout << screen[i][j] << "\t";
        cout << endl;
    }
    
    fillColor(screen, x, y, color);
    
    cout << "\nThe screen coordinates after coloring are : \n";
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++)
            cout << screen[i][j] << "\t";
        cout << endl;
    }
}

ผลลัพธ์

The initial screen coordinates are :
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

The screen coordinates after coloring are :
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   R   R   R   R   B   W   B
B   W   W   R   R   B   W   B
B   W   W   R   R   R   R   B
W   B   W   W   W   R   W   W
W   W   B   B   W   R   R   W