C++ में फ्लड फिल एल्गोरिदम - पेंट में fill() कैसे लागू करें

समस्या विवरण

इस समस्या में, हमें एक 2D सरणी दी गई है जो 2-D स्क्रीन को दर्शाती है, स्क्रीन पर एक पिक्सेल के निर्देशांक जिसे रंग से भरा जाना है, और रंग। हमारा कार्य वर्तमान पिक्सेल और उन सभी आसन्न पिक्सेल को रंगना है जिनका वही रंग है।

पेंट में रंग भरना, हम एक रंग चुनते हैं और ब्रश के साथ दिए गए पिक्सेल पर क्लिक करते हैं।

उदाहरण

इनपुट: 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

आउटपुट: Y से जुड़े क्षेत्र को R से भर दिया जाता है

फ्लड फिल एल्गोरिदम

इस एल्गोरिदम में, पिक्सेल को नए रंग से भरा जाएगा जब यह पहले से चयनित पिछले रंग में हो। यदि पिछला रंग पिछले रंग नहीं है, तो उस पिक्सेल को भरा नहीं जाएगा। एक पिक्सेल भरने के बाद, यह अपने ऊपर, नीचे, बाएं और दाएं पिक्सेल की जांच करेगा कि वे भी वही करते हैं। यदि पड़ोसी पिक्सेल किसी भिन्न रंग का है, तो उसे छोड़ दें। तब तक फॉलो करें जब तक शुरुआती पिक्सेल के समान रंग के सभी आसन्न पिक्सेल रंग न जाएं। फिर फिलिंग एल्गोरिदम रोकें।

हल का दृष्टिकोण

समस्या को हल करने की एक विधि पुनरावर्ती दृष्टिकोण का उपयोग करना है। हम पहले पिक्सेल को खोजेंगे जिसे रंगना है फिर इसके 4 पड़ोसी पिक्सेल की जांच करेंगे। यदि समान रंग के हैं तो नए रंग से बदलें और वर्तमान पिक्सेल के पड़ोसियों के साथ दोहराएं। यदि पड़ोसी पिक्सेल किसी भिन्न रंग का है, तो उसे छोड़ दें। तब तक फॉलो करें जब तक शुरुआती पिक्सेल के समान रंग के सभी आसन्न पिक्सेल रंग न जाएं।

C++ कार्यान्वयन

#include <iostream> 
using namespace std; 

#define M 8
#define N 8

void floodFillUtil(char screen[][N], int x, int y, char oldColor, char newColor) {
    // सीमा जांच
    if (x < 0 || x >= M || y < 0 || y >= N)
        return;
    
    // रंग मेल नहीं खाता
    if (screen[x][y] != oldColor)
        return;
    
    // पहले से ही नया रंग
    if (screen[x][y] == newColor)
        return;
    
    // रंग भरें
    screen[x][y] = newColor;
    
    // 4 दिशाओं में पुनरावृत्ति
    floodFillUtil(screen, x + 1, y, oldColor, newColor);
    floodFillUtil(screen, x - 1, y, oldColor, newColor);
    floodFillUtil(screen, x, y + 1, oldColor, newColor);
    floodFillUtil(screen, x, y - 1, oldColor, newColor);
}

void floodFill(char screen[][N], int x, int y, char newColor) {
    char oldColor = screen[x][y];
    if (oldColor == newColor) return;
    floodFillUtil(screen, x, y, oldColor, newColor);
}

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 << "प्रारंभिक स्क्रीन निर्देशांक:\n";
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++)
            cout << screen[i][j] << "\t";
        cout << endl;
    }
    
    floodFill(screen, x, y, color);
    
    cout << "\nरंग भरने के बाद स्क्रीन निर्देशांक:\n";
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++)
            cout << screen[i][j] << "\t";
        cout << endl;
    }
    return 0;
}

आउटपुट

प्रारंभिक स्क्रीन निर्देशांक:
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

रंग भरने के बाद स्क्रीन निर्देशांक:
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

जटिलता विश्लेषण

• समय जटिलता: O(M × N) -orst स्थिति में सभी पिक्सेल विज़िट किए जाते हैं
• स्पेस जटिलता: O(M × N) - पुनरावर्ती स्टैक (खराब स्थिति)

विविधताएं

• 4-दिशात्मक (ऊपर, नीचे, बाएं, दाएं) - ऊपर दिखाया गया
• 8-दिशात्मक (विकर्ण सहित) - 8 पुनरावर्ती कॉल जोड़ें
• पुनरावृत्तिमूलक (BFS) - स्टैक ओवरफ्लो से बचने के लिए क्यू का उपयोग करें

स्टैक ओवरफ्लो चेतावनी

बड़े क्षेत्रों के लिए पुनरावर्ती संस्करण स्टैक ओवरफ्लो का कारण बन सकता है। उत्पादन कोड में BFS/क्यू-आधारित दृष्टिकोण का उपयोग करें।