Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में बाइनरी मैट्रिक्स में सबसे छोटा पथ


मान लीजिए हमारे पास N x N वर्ग ग्रिड है, जहां प्रत्येक सेल या तो खाली (0) या अवरुद्ध (1) है। शीर्ष-बाएं से नीचे-दाएं तक एक स्पष्ट पथ की लंबाई k होती है यदि और केवल यदि यह सेल्स C_1, C_2, ..., C_k से बना होता है जैसे कि:

  • आसन्न सेल्स C_i और C_{i+1} 8-दिशात्मक रूप से जुड़े हुए हैं (इसलिए वे अलग हैं और एक किनारे या कोने को साझा करते हैं)

  • C_1 स्थान (0, 0) पर है

  • C_k स्थान (N-1, N-1) पर है

  • यदि C_i (r, c) पर स्थित है, तो grid[r, c] खाली है या 0 रखता है

हमें शीर्ष-बाएं से नीचे-दाएं तक ऐसे सबसे छोटे स्पष्ट पथ की लंबाई ढूंढनी होगी। यदि ऐसा कोई पथ नहीं है, तो -1 लौटाएं।

उदाहरण के लिए, यदि ग्रिड इस तरह है:

000
110
110

नारंगी सेल्स पथ होंगे। लंबाई 4 है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे:

  • एक दिशा सरणी परिभाषित करें, यह 8 अलग-अलग दिशाओं में जाने के लिए 8 जोड़े रखेगी। इसलिए यह सरणी [[1,1], [1,-1], [-1,1], [1,0], [0,1], [-1,-1], [0,-1], [-1,0]] जैसी है

  • मुख्य भाग ग्रिड को इनपुट के रूप में लेगा, यह इस तरह कार्य करेगा:

  • पॉइंट्स की एक कतार q परिभाषित करें, n := पंक्तियों की संख्या

  • यदि grid[0, 0] 0 है, तो एक नया पॉइंट p(0, 0, 1) बनाएं, p को q में सम्मिलित करें, और grid[0, 0] := 1 बनाएं

  • जब तक q खाली नहीं है

    • curr := q से फ्रंट पॉइंट, q से फ्रंट पॉइंट हटाएं

    • x := curr का x मान, y := curr का y मान, c := curr का c मान

    • यदि x = n - 1 और y = n - 1, तो c लौटाएं

    • c को 1 से बढ़ाएं

    • i को 0 से 7 तक के लिए

      • X := x + d[i, 0], Y := y + d[i, 1]

      • यदि X 0 और n की सीमा में है और Y 0 और n की सीमा में है, और grid[X, Y] 0 है, तो

        • grid[X, Y] := 1

        • q में एक नया पॉइंट p (X, Y, c) सम्मिलित करें

  • -1 लौटाएं

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:

उदाहरण

#include <bits/stdc++.h>
using namespace std;

int d[8][2] = {{1, 1}, {1, -1}, {-1, 1}, {1, 0}, {0, 1}, {-1, -1}, {0, -1}, {-1, 0}};

struct point {
    int x, y, c;
    point(int a, int b, int z) {
        x = a;
        y = b;
        c = z;
    }
};

class Solution {
public:
    int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
        queue <point> q;
        int n = grid.size();
        if(!grid[0][0]) {
            q.push(point(0, 0, 1));
            grid[0][0] = 1;
        }
        while(!q.empty()) {
            point curr = q.front();
            q.pop();
            int x = curr.x;
            int y = curr.y;
            int c = curr.c;
            if(x == n-1 && y == n-1) return c;
            c++;
            for(int i = 0; i < 8; i++) {
                int X = x + d[i][0];
                int Y = y + d[i][1];
                if(X >= 0 && X < n && Y >= 0 && Y < n && !grid[X][Y]) {
                    grid[X][Y] = 1;
                    q.push(point(X, Y, c));
                }
            }
        }
        return -1;
    }
};

int main() {
    vector<vector<int>> v = {{0,0,0},{1,1,0},{1,1,0}};
    Solution ob;
    cout << (ob.shortestPathBinaryMatrix(v));
}

इनपुट

[[0,0,0],[1,1,0],[1,1,0]]

आउटपुट

4
  1. C++ में बाइनरी ट्री में सबसे लंबा जिगजैग पथ C++ में बाइनरी ट्री में सबसे लंबा जिगजैग पथ

    मान लीजिए हमारे पास एक बाइनरी ट्री रूट है, बाइनरी ट्री के लिए एक जिगजैग पथ इस प्रकार परिभाषित है: बाइनरी ट्री में किसी भी नोड और एक डायरेक्शन (या तो राइट या लेफ्ट) को चुनें। अगर वर्तमान डायरेक्शन राइट है तो करंट नोड के राइट चाइल्ड की ओर बढ़ें अन्यथा लेफ्ट चाइल्ड की ओर बढ़ें। फिर डायरेक्शन को राइट

  1. C++ में बाइनरी ट्री में अधिकतम पथ योग C++ में बाइनरी ट्री में अधिकतम पथ योग

    इस समस्या में, हमें एक बाइनरी ट्री दिया गया है जिसमें प्रत्येक नोड एक मान रखता है। हमारा कार्य बाइनरी ट्री के दो पत्तों के बीच अधिकतम पथ योग ढूंढने के लिए एक प्रोग्राम बनाना है। यहां, हमें एक पत्ते नोड से दूसरे पत्ते नोड तक का पथ ढूंढना है जो मानों का अधिकतम योग प्रदान करेगा। यह अधिकतम योग पथ रूट न

  1. C++ प्रोग्राम: बाइनरी ट्री में पहला सबसे छोटा रूट-टू-लीफ पथ प्रिंट करना C++ प्रोग्राम: बाइनरी ट्री में पहला सबसे छोटा रूट-टू-लीफ पथ प्रिंट करना

    दिए गए बाइनरी ट्री में प्रोग्राम को दिए गए कई पथों में से रूट से लीफ तक का सबसे छोटा पथ ढूंढना होगा। चूंकि हम ट्री को बाएं से दाएं ट्रैवर्स करते हैं, इसलिए यदि रूट से लीफ तक कई सबसे छोटे पथ हैं तो प्रोग्राम ट्री के बाएं तरफ पहले ट्रैवर्स किए गए सबसे छोटे पथ को प्रिंट करेगा। हम एक कतार (queue) का उपय