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

परिचय

एक मैट्रिक्स दिया गया है; मैट्रिक्स एक स्क्रीन को दर्शाता है। स्क्रीन का प्रत्येक तत्व (i, j) एक पिक्सेल को दर्शाता है, उस पिक्सेल का रंग विभिन्न संख्याओं से चिह्नित होता है। इस एल्गोरिदम में, पिक्सेल को नए रंग से भरा जाएगा जब वह पहले से चयनित पिछले रंग में हो। यदि पिछला रंग पिछला रंग नहीं है, तो वह पिक्सेल नहीं भरा जाएगा। एक पिक्सेल भरने के बाद, यह अपने ऊपर, नीचे, बाएं और दाएं पिक्सेल की जांच करेगा ताकि वही काम किया जा सके।

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

इनपुट और आउटपुट

इनपुट: स्क्रीन मैट्रिक्स: [8x8 मैट्रिक्स जिसमें रंग कोड हैं]
आउटपुट: फ्लड फिल के बाद स्क्रीन मैट्रिक्स [रंग 2 को रंग 3 से बदल दिया गया है निर्देशांक (4,4) से शुरू करके]

एल्गोरिदम

fillScreen(x, y, prevColor, newColor)
इनपुट: शुरू करने के लिए (x,y) निर्देशांक, पिछला रंग, और नया रंग
आउटपुट: स्क्रीन पिछले रंग से नए में बदलने के बाद, यदि संभव हो

Begin
    यदि (x, y) स्क्रीन रेंज में नहीं है, तो
        लौटें
    यदि (x, y) का रंग ≠ prevColor, तो
        लौटें
    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 < M; i++) {
        for (int j = 0; j < N; j++)
            cout << screen[i][j] << " ";
        cout << endl;
    }
    cout << endl;
    floodFill(x, y, newColor); // (4, 4) से शुरू करें, नए रंग 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