ग्रिड में रोबोट: बंद खानों से बचते हुए दाएँ/नीचे का रास्ता (जावा)

टीएल;डीआर

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

तुम शहर के ब्लॉक ग्रिड के उत्तर-पश्चिम कोने पर खड़े हो। चल सकते हो सिर्फ पूर्व या दक्षिण। कुछ चौराहे निर्माण के लिए बंद हैं। क्या दक्षिण-पूर्व कोने तक पहुँच सकते हो, और अगर हाँ तो किन चौराहों की कतार से?

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

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

---

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

छोटा शहर का नक्शा सोचो: पंक्तियों और स्तंभों में चौराहे:

• शुरुआत ऊपर-बाएँ चौराहे (0, 0) पर।
• लक्ष्य नीचे-दाएँ (r - 1, c - 1)।
• खुले चौराहे से सिर्फ दाएँ एक ब्लॉक या नीचे एक ब्लॉक। बाएँ नहीं, ऊपर नहीं, तिरछा नहीं।
• कुछ चौराहे बाड़ लगे हैं। उन पर खड़े नहीं हो सकते।
• शुरुआत से लक्ष्य तक कोई भी कानूनी सैर चाहिए, चौराहों की सूची के रूप में। सभी सैर या सबसे छोटी नहीं (सिर्फ दाएँ और नीचे हो तो हर रास्ते की लंबाई एक जैसी: ठीक (r - 1) + (c - 1) चालें)।

३×३ ग्रिड आज़माओ, बीच बंद:

S . .
. X .
. . E

एक रास्ता: दाएँ, दाएँ, नीचे, नीचे (ऊपरी किनारा फिर दायाँ)। दूसरा: नीचे, नीचे, दाएँ, दाएँ (बायाँ किनारा फिर निचला)। दोनों बीच से बचते हैं।

अगर ऊपरी पंक्ति और बायाँ स्तंभ शुरुआत के ठीक बाद बंद हों, लक्ष्य खुला होने पर भी फँस सकते हो। पहुँच यह नहीं कि “अंत खुला है?”; यह है कि “शुरुआत से दाएँ/नीचे से जुड़े खुले खानों की श्रृंखला है?”

---

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

इनपुट: r पंक्तियों और c स्तंभों का ग्रिड। हर खाना खुला या बंद। कोड में: true मतलब कदम रख सकते हो, false मतलब बंद। शुरुआत (0, 0)। लक्ष्य (r - 1, c - 1)।

आउटपुट: शुरुआत से लक्ष्य तक वैध रास्ते के बिंदुओं की सूची, या कोई रास्ता न हो तो null / खाली।

चालें: (row, col) से सिर्फ (row, col + 1) (दाएँ) या (row + 1, col) (नीचे), और सिर्फ जब लक्ष्य सीमा में हो और खुला हो।

बिंदु का आकार:

class Point {
    final int row;
    final int col;

    Point(int row, int col) {
        this.row = row;
        this.col = col;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof Point)) return false;
        Point p = (Point) o;
        return row == p.row && col == p.col;
    }

    @Override
    public int hashCode() {
        return 31 * row + col;
    }

    @Override
    public String toString() {
        return "(" + row + "," + col + ")";
    }
}

छोटे उदाहरण:

ग्रिड का आइडिया	रास्ता?	नोट
१×१ खुला	हाँ: (0,0)	शुरुआत = लक्ष्य
१×१ बंद	नहीं	शुरुआत पर खड़े नहीं हो सकते
२×२ सब खुला	हाँ	जैसे दाएँ फिर नीचे, या नीचे फिर दाएँ
२×२ सिर्फ (0,1) बंद	हाँ	नीचे फिर दाएँ जाना होगा
२×२ में (0,1) और (1,0) बंद	नहीं	शुरुआत की दोनों निकास बंद
शुरुआत या अंत बंद	नहीं	रास्ते में दोनों छोर शामिल

कोड से पहले साफ करो:

• इंडेक्स: पहले पंक्ति, फिर स्तंभ। बोलो maze[row][col]; बिना परिभाषा के “एक्स/वाई” न।
• शुरुआत ज़रूर खुली है? फिर भी जाँचो।
• एक रास्ता या सभी? इस समस्या में एक रास्ता।
• बंद खाने कैसे? बूलियन ग्रिड, 0/1 पूर्णांक, या निषिद्ध बिंदुओं का सेट: एक चुनो।
• खाली ग्रिड या नल? नल लौटाओ।

---

३. पहले सोचो

रिकर्शन चालों से मेल खाता है

खाना (r, c) से रास्ता है अगर खाना खुला है और:

• तुम लक्ष्य पर हो, या
• दाएँ पड़ोसी से रास्ता है, या
• नीचे पड़ोसी से रास्ता है।

पीछे से भी खोज सकते हो: लक्ष्य से शुरू करो; कोई खाना पहुँच में है अगर खुला है और ऊपर या बाएँ से उस तक आ सकते हो। वही एसिम्पटोटिक्स। शुरुआत से आगे बढ़ना रास्ता बनाते समय स्वाभाविक लगता है।

ब्रूट फोर्स घातांकीय है

हर कदम पर दो शाखाएँ। रास्ते में लगभग r + c कदम, इसलिए सादा खोज-वृक्ष सबसे बुरे में O(2^(r+c)) काम। बुरा और: कई रास्ते एक ही खाने पर आते हैं। अगर वह मृत अंत है, असफलता बार-बार मिलती है।

असफलताओं को मेमो करो

मुख्य सुधार: हर खाने पर एक बार पूछो “यहाँ से लक्ष्य तक रास्ता है?” नहीं जवाब असफल बिंदुओं के सेट (या द्वि-आयामी बूलियन मेमो) में रखो। अगर साबित हो चुका कि खाना लक्ष्य तक नहीं पहुँचता, फिर मत खोलो।

उस कैश से हर खाना नियत बार पूरी तरह देखा जाता है। समय O(r * c) पर गिरता है। जगह मेमो के लिए O(r * c) और रास्ते/रिकर्शन गहराई के लिए O(r + c)।

डीपी टेबल canReach[row][col] भी भर सकते हो लक्ष्य से नीचे-ऊपर, फिर शुरुआत से लालच से चलो (अगला खाना पहुँच में हो तो दाएँ या नीचे)। वही O(r * c)।

रास्ता बनाना

दो साफ तरीके:

१. नीचे जाते समय: यहाँ से रिकर्सिव कॉल सफल हो तो इस बिंदु को प्रत्यय के आगे जोड़ो (या अंत में जोड़कर उल्टा करो)। २. लक्ष्य से मूल की ओर: लक्ष्य पर शुरू, बाएँ और ऊपर आज़माओ; मूल तक उप-रास्ता मिले तो मौजूदा बिंदु जोड़ो।

दोनों ठीक। नीचे आगे खोज शुरुआत से, असफल खानों के सेट के साथ।

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

१. ३×३ बनाओ, बीच बंद करो। २. (0,0) से डीएफएस: दाएँ आज़माओ, रिकर्शन; नीचे आज़माओ, रिकर्शन। ३. दोनों दिशाएँ असफल हों तभी खाने को असफल चिह्नित करो। ४. (2,2) छूते ही सफलता ऊपर आती है और हर फ्रेम अपना बिंदु सूची में जोड़ता है।

---

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

शुरुआत से मेमो वाला डीएफएस। खुले खाने true।

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * Find one path from top-left to bottom-right.
 * Moves: right or down only. maze[r][c] == true means free.
 */
public class RobotInAGrid {

    public List<Point> getPath(boolean[][] maze) {
        if (maze == null || maze.length == 0 || maze[0].length == 0) {
            return null;
        }
        List<Point> path = new ArrayList<>();
        Set<Point> failed = new HashSet<>();
        if (findPath(maze, 0, 0, path, failed)) {
            return path;
        }
        return null;
    }

    /**
     * Returns true if there is a path from (row, col) to the goal.
     * On success, path contains points from (row, col) through the goal in order.
     */
    private boolean findPath(
            boolean[][] maze,
            int row,
            int col,
            List<Point> path,
            Set<Point> failed) {

        int rows = maze.length;
        int cols = maze[0].length;

        if (row < 0 || col < 0 || row >= rows || col >= cols || !maze[row][col]) {
            return false;
        }

        Point here = new Point(row, col);
        if (failed.contains(here)) {
            return false;
        }

        boolean atGoal = (row == rows - 1) && (col == cols - 1);

        if (atGoal
                || findPath(maze, row, col + 1, path, failed)
                || findPath(maze, row + 1, col, path, failed)) {
            // Recursion filled the suffix (right or down branch).
            // Add this cell at the front so the full list is start -> goal.
            path.add(0, here);
            return true;
        }

        failed.add(here);
        return false;
    }
}

path.add(0, here) क्रम शुरुआत → लक्ष्य रखता है। अगर सिर्फ O(१) जोड़ पसंद हो, लौटते समय धक्का दो और अंत में उल्टा करो, या लक्ष्य से पीछे इकट्ठा कर एक बार उल्टा करो।

रूप: नीचे से ऊपर डीपी फिर पुनर्निर्माण

public List<Point> getPathDp(boolean[][] maze) {
    if (maze == null || maze.length == 0 || maze[0].length == 0) {
        return null;
    }
    int rows = maze.length;
    int cols = maze[0].length;
    if (!maze[0][0] || !maze[rows - 1][cols - 1]) {
        return null;
    }

    // canReach[r][c]: can we reach the goal from (r, c)?
    boolean[][] canReach = new boolean[rows][cols];
    canReach[rows - 1][cols - 1] = true;

    for (int r = rows - 1; r >= 0; r--) {
        for (int c = cols - 1; c >= 0; c--) {
            if (!maze[r][c]) {
                canReach[r][c] = false;
                continue;
            }
            if (r == rows - 1 && c == cols - 1) {
                continue;
            }
            boolean right = (c + 1 < cols) && canReach[r][c + 1];
            boolean down = (r + 1 < rows) && canReach[r + 1][c];
            canReach[r][c] = right || down;
        }
    }

    if (!canReach[0][0]) {
        return null;
    }

    List<Point> path = new ArrayList<>();
    int r = 0;
    int c = 0;
    path.add(new Point(0, 0));
    while (r != rows - 1 || c != cols - 1) {
        if (c + 1 < cols && canReach[r][c + 1]) {
            c++;
        } else if (r + 1 < rows && canReach[r + 1][c]) {
            r++;
        } else {
            return null; // should not happen if table is correct
        }
        path.add(new Point(r, c));
    }
    return path;
}

वही बड़ा-ओ। जब रिकर्शन स्टैक के बिना क्रमिक कहानी चाहिए, अच्छा।

न्यूनतम धुआँ जाँच

boolean[][] open2 = {
    {true, true},
    {true, true}
};
// path length 3, e.g. (0,0)-(0,1)-(1,1) or (0,0)-(1,0)-(1,1)

boolean[][] blockedCenter = {
    {true, true, true},
    {true, false, true},
    {true, true, true}
};
// still possible via top-right or bottom-left corridor

boolean[][] wall = {
    {true, false},
    {false, true}
};
// null path: both exits from start blocked

---

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

तरीका	समय	अतिरिक्त जगह	नोट
सादा डीएफएस, बिना मेमो	सबसे बुरा O(२^(r+c))	O(r + c) स्टैक + रास्ता	मृत खाने दोबारा
मेमो डीएफएस (असफल सेट)	O(r * c)	O(r * c) मेमो + O(r + c) रास्ता/स्टैक	हर खाना एक बार
नीचे-ऊपर डीपी + चाल	O(r * c)	O(r * c) टेबल	बिना रिकर्शन; एक रास्ता
रास्ते की लंबाई (मिले तो)	-	O(r + c) बिंदु	हमेशा (r - 1) + (c - 1) + 1 खाने

इंटरव्यूअर चाहता है कि घातांकीय जाल का नाम लो, फिर मेमो सेट (या डीपी टेबल) दिखाओ जो खानों की संख्या में रैखिक बना दे।

---

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

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

• शुरुआत या लक्ष्य बंद: तुरंत असफल।
• १×१ खुला: रास्ता वही एक खाना।
• एक पंक्ति या एक स्तंभ: एक गलियारा; कोई भी रुकावट काट देती है।
• नल या शून्य आकार: नल लौटाओ; maze[0] पर इंडेक्स न काटो।
• असमान पंक्ति लंबाई: आयत मानो; नहीं तो maze[i].length जाँचो।
• बिना परिभाषा एक्स/वाई: row और col पसंद करो।

आम गलतियाँ:

१. मेमो भूलना। कोड सही दिखे, बड़े खुले ग्रिड पर अंत के पास कई रुकावटों से समय खत्म। २. सिर्फ चक्रों के लिए “देखा” मेमो। सिर्फ दाएँ/नीचे पर चक्र नहीं, फिर भी असफल खानों का कैश चाहिए क्योंकि कई माता-पिता एक बच्चे को बाँटते हैं। ३. बहुत जल्दी असफल चिह्न (दोनों दिशाएँ आज़माने से पहले)। ४. लक्ष्य पर एक-कम गलती (rows बनाम rows - 1)। ५. ग्रिड को देखा हुआ म्यूटेट बिना वापस लाए, दूसरी कॉल फेल। ६. गलत क्रम में बिंदु (लक्ष्य → शुरुआत) बिना उल्टे। ७. true/false मिलाकर बंद को खुला मानना।

---

७. दोस्त को समझाओ सार

ग्रिड पर रोबोट, इंटरव्यू संस्करण:

१. शुरुआत ऊपर-बाएँ, लक्ष्य नीचे-दाएँ। चालें: सिर्फ दाएँ या नीचे। कुछ खाने वर्जित। २. रिकर्शन: खुले खाने से दाएँ आज़माओ, नीचे आज़माओ; लक्ष्य पहुँचे तो सफलता। ३. बिना कैश, एक ही मृत खाना कई माता-पिता से: घातांकीय समय। ४. मेमो: याद रखो कौन से खाने लक्ष्य नहीं पहुँचते। हर खाना एक बार → O(r * c)। ५. सफल लौट पर बिंदु जोड़कर एक रास्ता बनाओ (या डीपी टेबल + लालची चाल)। ६. शुरुआत/लक्ष्य खुले, सीमाएँ, खाली इनपुट जाँचो।

अगर छोटा भूलभुलैया बनाकर असफल खाने को चिह्नित कर सकते हो ताकि दूसरा माता-पिता छोड़ दे, और बिना इंडेक्स बग के मेमो वाला रिकर्सिव मेथड लिख सकते हो, समस्या ८.२ तुम्हारी है। अध्याय में आगे: मैजिक इंडेक्स।

---

सीरीज़

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