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

भूलभुलैया III - C++


मान लीजिए एक भूलभुलैया है जिसमें खाली स्थान और दीवारें हैं और उस भूलभुलैया में एक गेंद भी है। गेंद ऊपर (u), नीचे (d), बाएं (l) या दाएं (r) दिशाओं में लुढ़ककर खाली स्थानों से गुजर सकती है, लेकिन यह दीवार से टकराने तक लुढ़कती रहती है। जब गेंद रुकती है, तो यह अगली दिशा चुन सकती है। उस भूलभुलैया में एक छेद भी है। गेंद छेद में गिर जाएगी यदि यह छेद पर लुढ़कती है।

तो यदि हमारे पास गेंद की स्थिति, छेद की स्थिति और भूलभुलैया है, तो हमें यह पता लगाना होगा कि गेंद सबसे छोटी दूरी तय करके छेद में कैसे गिर सकती है। यहां दूरी को गेंद द्वारा शुरुआत (शामिल नहीं) से छेद (सम्मिलित) तक तय किए गए खाली स्थानों की संख्या से परिभाषित किया गया है।

चलती दिशाओं को 'u', 'd', 'l' और 'r' का उपयोग करके लौटाएं। चूंकि कई अलग-अलग सबसे छोटे तरीके हो सकते हैं, और आउटपुट लेक्सिकोग्राफिक रूप से सबसे छोटा तरीका होना चाहिए। यदि गेंद छेद तक नहीं पहुंच सकती, तो "impossible" प्रदर्शित करें।

यहां भूलभुलैया को एक बाइनरी मैट्रिक्स द्वारा दर्शाया गया है। 1 का अर्थ दीवार है और 0 का अर्थ खाली स्थान। गेंद और छेद के निर्देशांक पंक्ति और स्तंभ इंडेक्स द्वारा दर्शाए गए हैं।

तो, यदि इनपुट इस तरह है

भूलभुलैया III - C++

तो आउटपुट 'lul' होगा क्योंकि बाएं चलें, फिर ऊपर फिर बाएं, एक अन्य परिणाम 'ul' हो सकता है, ऊपर फिर बाएं, दोनों की लंबाई 6 है, लेकिन यह 'lul' से लेक्सिकोग्राफिक रूप से छोटा नहीं है

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

  • Data नामक एक डेटा प्रकार परिभाषित करें, जो दूरी, एक स्ट्रिंग d और निर्देशांक x,y लेगा।

  • आकार 4 x 2 का एक ऐरे dir परिभाषित करें := {{1, 0}, {0, - 1}, {0, 1}, { - 1, 0}}

  • आकार 4 का एक ऐरे dirst परिभाषित करें := {'d', 'l', 'r', 'u'}

  • एक फ़ंक्शन ok() परिभाषित करें, जो x1, y1, x2, y2 लेगा,

  • true लौटाएं यदि x1, x2 के समान है AND y1, y2 के समान है

  • मुख्य विधि से निम्नलिखित करें −

  • n := भूलभुलैया का पंक्ति आकार

  • m := (यदि n शून्येतर है, तो भूलभुलैया का स्तंभ आकार, अन्यथा 0)

  • एक प्राथमिकता कतार pq परिभाषित करें

  • (0, ball[0], ball[1], "") के साथ नया डेटा pq में डालें

  • आकार n x m का एक 2D ऐरे visited परिभाषित करें

  • जब तक (pq खाली नहीं है), करें −

    • curr := pq का शीर्ष तत्व

    • x := curr.x

    • y := curr.y

    • dist := curr.dist

    • d := curr.d

    • यदि ok(x, y, hole[0], hole[1]), तो −

      • d लौटाएं

    • visited[x, y] := true

    • pq से तत्व हटाएं

    • k := 0 से आरंभ करें, जब k − 4, अद्यतन करें (k को 1 से बढ़ाएं), करें −

      • nx := x, ny := y

      • tempDist := 0

      • जब तक nx + dir[k, 0] < n और nx + dir[k, 0] >= 0 और ny + dir[k, 1] < m और ny + dir[k, 1] >= 0 और maze[nx + dir[k, 0], ny + dir[k, 1]] 0 है, करें −

        • nx := nx + dir[k, 0]

        • ny := ny + dir[k, 1]

        • (tempDist को 1 से बढ़ाएं)

        • यदि ok(nx, ny, hole[0], hole[1]), तो −

          • लूप से बाहर आएं

      • यदि visited[nx, ny] शून्य है, तो −

        • नया Data(dist + tempDist, nx, ny, d + dirst[k]) pq में डालें

    • "impossible" लौटाएं

उदाहरण 

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

#include <bits/stdc++.h> using namespace std; int dir[4][2] = {{1, 0}, {0, -1}, {0, 1}, {-1, 0}}; char dirst[4] = {'d', 'l', 'r', 'u'}; class Solution { public:    struct Data {       int dist;       string d;       int x, y;       Data(int a, int b, int c, string s) {          d = s;          dist = a;          x = b;          y = c;       }    };    struct Comparator {       bool operator()(Data a, Data b) {          return a.dist != b.dist ? !(a.dist < b.dist) : !(a.d < b.d);       }    };    bool ok(int x1, int y1, int x2, int y2) { return x1 == x2 && y1 == y2; }    string findShortestWay(vector<vector<int>> &maze, vector<int>&ball,       vector<int> &hole) {          int n = maze.size();          int m = n ? maze[0].size() : 0;          priority_queue<vector<Data>, vector<Data>, Comparator> pq;          pq.push(Data(0, ball[0], ball[1], ""));          vector<vector<bool>> visited(n, vector<bool>(m));          while (!pq.empty()) {             Data curr = pq.top();             int x = curr.x;             int y = curr.y;             int dist = curr.dist;             string d = curr.d;             if (ok(x, y, hole[0], hole[1])) {                return d;             }             visited[x][y] = true;             pq.pop();             for (int k = 0; k < 4; k++) {                int nx = x;                int ny = y;                int tempDist = 0;                while (nx + dir[k][0] < n && nx + dir[k][0] >= 0 && ny + dir[k][1] < m && ny + dir[k][1] >= 0 && !maze[nx + dir[k][0]][ny + dir[k][1]]) {                   nx += dir[k][0];                   ny += dir[k][1];                   tempDist++;                   if (ok(nx, ny, hole[0], hole[1]))                      break;                }                if (!visited[nx][ny]) {                   pq.push(Data(dist + tempDist, nx, ny, d + dirst[k]));                }             }          }          return "impossible";    } }; main() {    Solution ob;    vector<vector<int>> v = {       {0, 0, 0, 0, 0},       {1, 1, 0, 0, 1},       {0, 0, 0, 0, 0},       {0, 1, 0, 0, 1},       {0, 1, 0, 0, 0}};    vector<int> v1 = {4, 3}, v2 = {0, 1};    cout << (ob.findShortestWay(v, v1, v2)); }

इनपुट

vector<vector<int>> v = {{0, 0, 0, 0, 0}, {1, 1, 0, 0, 1}, {0, 0, 0, 0, 0}, {0, 1, 0, 0, 1}, {0, 1, 0, 0, 0}}; vector<int> v1 = {4, 3}, v2 = {0, 1};

आउटपुट

lul

  1. C++ में भूलभुलैया समस्या का समाधान C++ में भूलभुलैया समस्या का समाधान

    समस्या विवरण मान लीजिए एक गेंद एक भूलभुलैया में है जिसमें खाली स्थान और दीवारें हैं। गेंद किसी भी दिशा में (ऊपर, नीचे, बाएं, दाएं) लुढ़ककर खाली रास्तों से गुजर सकती है, लेकिन यह तब तक नहीं रुकेगी जब तक यह दीवार से न टकरा जाए। जब गेंद रुकती है, तो यह अगली दिशा चुन सकती है। हमें गेंद की प्रारंभिक स्

  1. C++ में स्पाइरल मैट्रिक्स III (Spiral Matrix III) C++ में स्पाइरल मैट्रिक्स III (Spiral Matrix III)

    मान लीजिए हमारे पास R पंक्तियों और C स्तंभों वाला एक 2-आयामी ग्रिड है, हम (r0, c0) से शुरू करते हैं और पूर्व की ओर मुख किए होते हैं। यहां, ग्रिड का उत्तर-पश्चिम कोना पहली पंक्ति और स्तंभ पर है, और दक्षिण-पूर्व कोना अंतिम पंक्ति और स्तंभ पर है। हम इस ग्रिड में हर स्थिति को देखने के लिए दक्षिणावर्त स

  1. C++ में बल्ब स्विचर III C++ में बल्ब स्विचर III

    मान लीजिए हमारे पास n बल्ब्स वाला एक कमरा है, ये 1 से n तक नंबरेड हैं, बाएं से दाएं एक पंक्ति में व्यवस्थित। प्रारंभ में, सभी बल्ब्स बंद हैं। मोमेंट k पर (k के लिए 0 से n-1 की रेंज में), हम light[k] बल्ब को ऑन करते हैं। एक बल्ब केवल तभी नीला होता है जब वह ऑन हो और उसके सभी पिछले बल्ब (बाएं तरफ) भी