อัลกอริธึมการเติมน้ำท่วม – วิธีใช้งาน fill() ในโปรแกรมระบายสีใน C ++

ในปัญหานี้เราได้รับอาร์เรย์ 2 มิติที่แสดงหน้าจอ 2 มิติซึ่งเป็นพิกัดของพิกเซลบนหน้าจอที่จะเติมด้วยสีและสี งานของเราคือสร้างโปรแกรมเพื่อ ระบายสีพิกเซลปัจจุบันและพิกเซลที่อยู่ติดกันทั้งหมดที่มีสีนั้น

การลงสีในเพ้นท์ เราจะเลือกสีและคลิกที่พิกเซลที่กำหนดด้วยพู่กัน

มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน

อินพุต:ฉาก[][] ={{W, B, W, 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 , 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}};

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

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

แนวทางการแก้ปัญหา

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

ตัวอย่าง

โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา

#includeใช้เนมสเปซ std;#define M 8#define N 8void fillColorAdj(char screen[][N], int x, int y, char oldColor, char color){ if (x <0 || x>=M || y <0 || y>=N) กลับ; ถ้า (screen[x][y] !=oldColor) กลับมา; ถ้า (หน้าจอ[x][y] ==สี) กลับ; หน้าจอ[x][y] =สี; fillColorAdj (หน้าจอ, x+1, y, สีเก่า, สี); fillColorAdj (หน้าจอ, x-1, y, สีเก่า, สี); fillColorAdj (หน้าจอ, x, y+1, สีเก่า, สี); fillColorAdj (หน้าจอ, x, y-1, oldColor, สี);}เป็นโมฆะ fillColor (หน้าจอถ่าน [][N], int x, int y, สีถ่าน){ ถ่าน oldColor =หน้าจอ[x][y]; if(oldColor==color) กลับมา; fillColorAdj(หน้าจอ, x, y, oldColor, สี);}int main(){ หน้าจอถ่าน[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; สีถ่าน ='R'; cout<<"พิกัดหน้าจอเริ่มต้นคือ :\n"; สำหรับ (int i=0; i 
ผลลัพธ์
 
 พิกัดหน้าจอเริ่มต้นคือ :W W B W W W W WW W W W W W W B BW B B W W B W WW Y Y Y Y B W BB W W Y Y B W BB W W Y Y Y Y Y BW B W W W Y W WW W B B W Y Y W พิกัดหน้าจอหลังจากระบายสีคือ W W B W W W W WW W W B W R W R W B W R W B W B W R W B