पेंट फिल: डीएफएस या बीएफएस से रंग क्षेत्र भरना (जावा)

टीएल;डीआर

• समस्या: डेटा संरचनाओं और एल्गोरिदम के लिए समय और स्थान जटिलता (टाइम एंड स्पेस कॉम्प्लेक्सिटी) का अनुकूलन।
• दृष्टिकोण: शुरुआती लोगों के लिए सीटीसीआई शैली की समस्या ८.१०: रंगों की द्विआयामी स्क्रीन पर पेंट बकेट फिल। जावा में रिकर्सिव डीएफएस या इटरेटिव बीएफएस से जुड़े क्षेत्र को नया रंग दो।
• जटिलता: सीमांत मामलों (एज केसेस) के प्रबंधन के साथ इष्टतम समय और मेमोरी संतुलन।

इमेज एडिटर में पेंट बकेट टूल होता है। एक पिक्सेल पर क्लिक करो, नया रंग चुनो, और पुराने रंग का पूरा जुड़ा ब्लॉब पलट जाता है। स्क्रीन रंग मानों का द्विआयामी ऐरे है। क्लिक पंक्ति और स्तंभ है। काम: ऊपर, नीचे, बाएँ, दाएँ कदम रखकर, मूल रंग छोड़े बिना पहुँच सकने वाले हर पिक्सेल को नया रंग देना।

यह पोस्ट जावा में शुरुआती लोगों के लिए मूल शिक्षण है। क्लासिक फ्लड फिल इंटरव्यू सवालों का परिवार, किताब की नकल नहीं। सीटीसीआई जावा सीरीज़ का हिस्सा। अध्याय ८, रिकर्शन और डायनामिक प्रोग्रामिंग: इस बार मेमो टेबल नहीं, ग्रिड पर ग्राफ सर्च।

---

१. रोज़मर्रा की उपमा

रंग के बड़े धब्बों वाली टाइल फर्श सोचो। तुम एक नीली टाइल पर खड़े हो और हर उस नीली टाइल को लाल रंगना चाहते हो जहाँ किनारे साझा करके पैदल पहुँच सको (सिर्फ कोना नहीं)।

• क्लिक वाली टाइल से शुरू करो। याद रखो वह नीली थी।
• उसे लाल रंग दो।
• चार पड़ोसी देखो: उत्तर, दक्षिण, पूर्व, पश्चिम।
• जो पड़ोसी अभी भी नीला हो, वहाँ जाओ और वही करो।
• जब पड़ोसी सीमा से बाहर हो, पहले से लाल हो, या कभी नीला न रहा हो (दीवार, हरा धब्बा, कुछ भी), रुक जाओ।

जब तक इंटरव्यूअर आठ-तरफ़ा कनेक्टिविटी न माँगे, तिरछे मत कूदो। जो टाइलें मूल रंग की नहीं थीं, उन्हें दोबारा मत रंगो। यही फ्लड फिल है: रंग की सीमा तक जुड़ा क्षेत्र बढ़ता है।

अगर क्लिक पहले से नया रंग है, कुछ मत करो। नीले को नीला रंगते रहना असली बग है (अनंत रिकर्शन या घूमता बीएफएस)।

---

२. सादा समस्या कथन

इनपुट:

• screen: रंगों का द्विआयामी ऐरे (पूर्णांक, एनम, या अक्षर; इंटरव्यू में अक्सर int[][] या Color[][])
• r, c: क्लिक निर्देशांक
• newColor: भरने वाला रंग

आउटपुट: वही स्क्रीन, जिसमें (r, c) पर मूल रंग का जुड़ा क्षेत्र newColor से बदला हो। इन-प्लेस बदलो या ऐरे लौटाओ; बोल दो।

कनेक्टिविटी (इस समस्या का डिफ़ॉल्ट): चार दिशाएँ, सिर्फ किनारे वाले पड़ोसी:

(-1, 0), (1, 0), (0, -1), (0, 1)

सिग्नेचर का आकार:

void paintFill(int[][] screen, int r, int c, int newColor);
// or with an enum / Color type
boolean paintFill(Color[][] screen, int r, int c, Color newColor);

बूलियन लौटाना (क्या भरा?) कुछ किताबी स्केच का वैकल्पिक पॉलिश है। वॉइड म्यूटेशन काफी है।

इंटरव्यू में साफ करो:

• चार-तरफ़ा या आठ-तरफ़ा पड़ोसी?
• सीमा नियम और खाली स्क्रीन?
• (r, c) सीमा से बाहर हो तो क्या?
• वही रंग क्लिक: कोई काम नहीं?
• रंग नल हो सकते हैं (अगर ऑब्जेक्ट टाइप)?
• इनपुट बदलना या कॉपी?

छोटा उदाहरण:

पहले (क्लिक (1,1), नया रंग = 9):

  1 1 1 2
  1 1 0 2
  1 0 1 2

बाद (ऊपर-बाएँ १-क्षेत्र का चार-तरफ़ा फिल):

  9 9 9 2
  9 9 0 2
  9 0 1 2

नीचे बीच का अकेला १ रहता है। भरे क्षेत्र से सिर्फ कोना साझा करता है, किनारा नहीं।

---

३. पहले सोचो

यह ग्राफ सर्च है

हर सेल एक नोड है। पड़ोसी तक किनारा तब है जब वह सीमा में हो और अभी भी मूल रंग पर हो। फ्लड फिल: "शुरू सेल के जुड़े घटक का हर नोड देखो, और रंग बदलो।"

डीएफएस (रिकर्शन या साफ स्टैक) और बीएफएस (क्यू) दोनों चलते हैं। इंटरव्यूअर दोनों मानते हैं। ग्राफ फ्रेमिंग ज़ोर से बोलो; दिखाता है कि सिर्फ पेंट-टूल की कहानी नहीं दोहरा रहे।

पहले मूल रंग पकड़ो

oldColor = screen[r][c]
if oldColor == newColor: return
// then flood only cells equal to oldColor

अगर oldColor पढ़ने से पहले शुरू रंग बदल दो, लक्ष्य खो जाता है। अगर रंग एक जैसे हों तो जल्दी बाहर न निकलो, तो जब oldColor == newColor हो हर रंगा सेल अभी भी "मैच" करता है और रिकर्शन कभी नहीं रुकती। गार्ड लगाओ।

रिकर्सिव डीएफएस स्केच

function fill(r, c):
  if out of bounds: return
  if screen[r][c] != oldColor: return
  screen[r][c] = newColor
  fill(r-1, c); fill(r+1, c); fill(r, c-1); fill(r, c+1)

प्रवेश:

oldColor = screen[r][c]
if oldColor == newColor: return
fill(r, c)

इटरेटिव बीएफएस स्केच

queue.push(start)
screen[start] = newColor
while queue not empty:
  cell = queue.pop
  for each neighbor:
    if in bounds and screen[neighbor] == oldColor:
      screen[neighbor] = newColor
      queue.push(neighbor)

क्यू में डालते समय रंगो (या विज़िटेड मार्क करो) ताकि एक सेल दो बार न जाए। ग्रिड पर oldColor से हटना ही विज़िटेड मार्क है। अलग boolean[][] ज़रूरी नहीं।

इंटरव्यू में डीएफएस बनाम बीएफएस

	रिकर्सिव डीएफएस	इटरेटिव बीएफएस
कोड लंबाई	छोटा	थोड़ा ज़्यादा (क्यू + दिशाएँ)
स्टैक जोखिम	लंबे साँप जैसे क्षेत्र पर कॉल स्टैक फट सकता है	हीप पर क्यू; बड़ी स्क्रीन पर सुरक्षित
क्रम	गहराई पहले	स्तर क्रम; अंतिम चित्र वही

इंटरव्यू आकार पर दोनों ठीक। एन × एम एक-रंग स्क्रीन पर डीएफएस की गहराई लगभग एन*एम बताओ।

यह "रिकर्शन और डायनामिक प्रोग्रामिंग" में क्यों

स्वाभाविक लेखन रिकर्सिव है। कोई भव्य मेमो टेबल नहीं। "उपसमस्याएँ" पड़ोसी हैं। फिर भी अध्याय से मेल: ग्रिड पर रिकर्शन, रोबोट पथ और भूलभुलैया फ्लड का परिवार।

व्हाइटबोर्ड स्केच

१. ३×४ ग्रिड बनाओ जिसमें रंग १ का धब्बा और दूसरे रंग हों। २. क्लिक मार्क करो। लिखो old = 1, new = 9। ३. शुरू रंग बदलो, फिर चार दिशाएँ पीछा करो। ४. वह सेल दिखाओ जो फ्लड रोकता है (अलग रंग या सीमा)। ५. old == new पर जल्दी बाहर निकलना नोट करो।

---

४. जावा समाधान

साझा हेल्पर

static final int[][] DIRS = {
    {-1, 0}, {1, 0}, {0, -1}, {0, 1}
};

static boolean inBounds(int[][] screen, int r, int c) {
    return r >= 0 && r < screen.length
        && c >= 0 && c < screen[0].length;
}

शिक्षण कोड गैर-खाली आयताकार स्क्रीन मानता है। प्रोडक्शन में खाली ऐरे गार्ड करो।

रिकर्सिव डीएफएस

/**
 * Paint-bucket fill: recolor the 4-connected region of screen[r][c].
 * Mutates screen in place.
 */
void paintFillDfs(int[][] screen, int r, int c, int newColor) {
    if (screen == null || screen.length == 0 || screen[0].length == 0) {
        return;
    }
    if (!inBounds(screen, r, c)) {
        return;
    }
    int oldColor = screen[r][c];
    if (oldColor == newColor) {
        return;
    }
    fill(screen, r, c, oldColor, newColor);
}

void fill(int[][] screen, int r, int c, int oldColor, int newColor) {
    if (!inBounds(screen, r, c)) {
        return;
    }
    if (screen[r][c] != oldColor) {
        return;
    }
    screen[r][c] = newColor;
    for (int[] d : DIRS) {
        fill(screen, r + d[0], c + d[1], oldColor, newColor);
    }
}

इटरेटिव बीएफएस

void paintFillBfs(int[][] screen, int r, int c, int newColor) {
    if (screen == null || screen.length == 0 || screen[0].length == 0) {
        return;
    }
    if (!inBounds(screen, r, c)) {
        return;
    }
    int oldColor = screen[r][c];
    if (oldColor == newColor) {
        return;
    }

    java.util.ArrayDeque<int[]> q = new java.util.ArrayDeque<>();
    screen[r][c] = newColor;
    q.add(new int[] {r, c});

    while (!q.isEmpty()) {
        int[] cell = q.removeFirst();
        int cr = cell[0];
        int cc = cell[1];
        for (int[] d : DIRS) {
            int nr = cr + d[0];
            int nc = cc + d[1];
            if (inBounds(screen, nr, nc) && screen[nr][nc] == oldColor) {
                screen[nr][nc] = newColor;
                q.add(new int[] {nr, nc});
            }
        }
    }
}

क्यू के रूप में ऐरेडीक्यू साफ और काफी तेज़ है। व्हाइटबोर्ड पर मैन्युअल लिंक्ड क्यू भी ठीक।

वैकल्पिक कलर एनम शैली

कुछ लेखन "असली" पिक्सेल जैसे एनम इस्तेमाल करते हैं:

enum Color { RED, GREEN, BLUE, YELLOW }

boolean paintFill(Color[][] screen, int r, int c, Color newColor) {
    if (screen == null || screen.length == 0) {
        return false;
    }
    if (!inBoundsColor(screen, r, c)) {
        return false;
    }
    Color oldColor = screen[r][c];
    if (oldColor == newColor) {
        return false;
    }
    fillColor(screen, r, c, oldColor, newColor);
    return true;
}

void fillColor(Color[][] screen, int r, int c, Color oldColor, Color newColor) {
    if (!inBoundsColor(screen, r, c)) {
        return;
    }
    if (screen[r][c] != oldColor) {
        return;
    }
    screen[r][c] = newColor;
    fillColor(screen, r - 1, c, oldColor, newColor);
    fillColor(screen, r + 1, c, oldColor, newColor);
    fillColor(screen, r, c - 1, oldColor, newColor);
    fillColor(screen, r, c + 1, oldColor, newColor);
}

boolean inBoundsColor(Color[][] screen, int r, int c) {
    return r >= 0 && r < screen.length
        && c >= 0 && c < screen[0].length;
}

वही एल्गोरिदम। जादुई पूर्णांक की जगह "रंग" बोलते समय एनम अच्छे लगते हैं।

न्यूनतम स्मोक जाँच

int[][] g = {
    {1, 1, 1, 2},
    {1, 1, 0, 2},
    {1, 0, 1, 2}
};
paintFillDfs(g, 1, 1, 9);
assert g[0][0] == 9 && g[0][1] == 9 && g[0][2] == 9;
assert g[1][0] == 9 && g[1][1] == 9;
assert g[2][0] == 9;
assert g[1][2] == 0; // not part of the 1-region via edges
assert g[2][1] == 0;
assert g[2][2] == 1; // diagonal only; four-way leaves it
assert g[0][3] == 2;

int[][] same = {{3, 3}, {3, 3}};
paintFillBfs(same, 0, 0, 3); // no-op, must not hang
assert same[1][1] == 3;

int[][] one = {{5}};
paintFillBfs(one, 0, 0, 7);
assert one[0][0] == 7;

---

५. जटिलता तालिका

तरीका	समय	अतिरिक्त जगह	नोट
रिकर्सिव डीएफएस	ओ(आर * सी)	सबसे खराब ओ(आर * सी) कॉल स्टैक	क्षेत्र का हर सेल एक बार; सबसे बड़ा क्षेत्र पूरी स्क्रीन
इटरेटिव बीएफएस	ओ(आर * सी)	सबसे खराब ओ(आर * सी) क्यू	वही विज़िट सीमा; जेवीएम स्टैक जोखिम नहीं
आठ-तरफ़ा रूप	ओ(आर * सी)	वही	प्रति सेल ज़्यादा किनारे; फिर भी सेलों में रैखिक

प्रति सेल नियत काम से ज़्यादा कभी नहीं। बड़े फिल पर रिकर्सिव डीएफएस के लिए ओ(१) जगह मत बोलो; स्टैक असली है।

---

६. किनारे के केस और आम गलतियाँ

इंटरव्यूअर ये छेड़ते हैं:

• क्लिक रंग पहले से नया: तुरंत लौटो। नहीं तो अनंत रिकर्शन / क्यू।
• सीमा से बाहर क्लिक: लौटो; जब तक एपीआई न कहे, थ्रो मत करो।
• १×१ स्क्रीन: रंग अलग हों तो एक असाइनमेंट।
• पूरी स्क्रीन एक रंग: हर सेल पलटता है; डीएफएस गहराई बहुत हो सकती है।
• क्षेत्र किनारे छूता हो: हर पड़ोसी पर सीमा जाँच, सिर्फ शुरू पर नहीं।
• टेढ़ी पंक्तियाँ: शिक्षण कोड आयत मानता है; पंक्तियाँ अलग लंबाई हों तो बोलो।
• आठ बनाम चार: गलत तिरछा ब्लीड जवाब बदलता है (उदाहरण सेल (2,2) देखो)।
• oldColor बचाने से पहले रंग बदलना: मैच क्या करें पता नहीं चलता।

आम गलतियाँ:

१. oldColor == newColor गार्ड भूलना। २. फैलते समय == oldColor की जगह != newColor जाँचना (हर गैर-नए सेल में घुस जाओगे)। ३. चार दिशाओं में एक दिशा छूटना। ४. गलती से आठ दिशाएँ इस्तेमाल। ५. बिना रंगे क्यू में डालना (बीएफएस हमेशा घूमता) या बिना विज़िट मार्क रंगना। ६. सीमा ऑफ-बाय-वन (< length की जगह <= length)। ७. स्क्रीन वर्ग मानना जब चौड़ाई सिर्फ screen[0].length हो (आयत पर ठीक; धारणा बोलो)।

---

७. दोस्त को समझाने वाला सार

पेंट फिल एक साँस में:

१. स्क्रीन रंगों की ग्रिड है। एक सेल पर क्लिक और नया रंग। २. oldColor याद रखो। अगर पहले से newColor के बराबर है, रुक जाओ। ३. ऊपर/नीचे/बाएँ/दाएँ कदमों से oldColor पर रहकर पहुँचने वाला हर सेल रंगो। ४. रिकर्सिव डीएफएस या बीएफएस क्यू: अंतिम तस्वीर वही। ५. सेल में घुसते समय रंगो (या विज़िटेड मार्क) ताकि दो बार प्रोसेस न हो। ६. समय और जगह भरे क्षेत्र के आकार में रैखिक (सबसे बुरा: पूरी ग्रिड)।

अगर ३×४ उदाहरण हाथ से चला सको, जल्दी-बाहर गार्ड लिख सको, और बता सको कि चार-तरफ़ा तिरछे सेल को क्यों छोड़ता है, तो समस्या ८.१० तुम्हारी है। अध्याय में आगे सिक्कों जैसा गिनती वाला डायनामिक प्रोग्रामिंग है।

---

सीरीज़

• गाइड: सीटीसीआई सीरीज़ गाइड
• पिछला: पैरेंस
• अगला: कॉइन्स