อัลกอริธึมเติมน้ำท่วม

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

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

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

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

อัลกอริทึม

fillScreen(x, y, prevColor, newColor)

ป้อนข้อมูล: พิกัด (x,y) เพื่อเริ่มต้น สีก่อนหน้า และสีใหม่

ผลลัพธ์ − หน้าจอหลังจากเปลี่ยนสีจากเดิมเป็นใหม่ ถ้าเป็นไปได้

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

ตัวอย่าง

#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;
   }
}

ผลลัพธ์

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