C++ . में भूलभुलैया III

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

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

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

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

तो, अगर इनपुट पसंद है

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

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

• डेटा नामक एक डेटा प्रकार को परिभाषित करें, यह दूरी लेगा, एक स्ट्रिंग डी और समन्वय एक्स, वाई।

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

• आकार के अनुसार एक सरणी परिभाषित करें:4 :={'d', 'l', 'r', 'u'}

• फ़ंक्शन को परिभाषित करें ठीक (), इसमें x1, y1, x2, y2,

  लगेगा

• यदि x1 x2 के समान है और y1 y2 के समान है, तो सही लौटें

• मुख्य विधि से निम्न कार्य करें -

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

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

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

• pq में नया डेटा डालें (0, बॉल[0], बॉल[1], "")

• n x m आकार की विज़िट की गई एक 2D सरणी परिभाषित करें

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

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

  • x :=curr.x

  • y:=curr.y

  • जिला :=curr.dist

  • डी:=curr.d

  • अगर ठीक है (x, y, छेद [0], छेद [1]), तो -

    • वापसी d

  • विज़िट किया गया [x, y] :=सच

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

  • k :=0 को इनिशियलाइज़ करने के लिए, जब k -4, अपडेट करें (k को 1 से बढ़ाएँ), करें -

    • एनएक्स:=एक्स, एनवाई:=वाई

    • tempDist:=0

    • जबकि एनएक्स + डीआईआर [के, 0] <एन और एनएक्स + डीआईआर [के, 0]> =0 और एनई + डीआईआर [के, 1] <एम और एनई + डीआईआर [के, 1]> =0 और भूलभुलैया [एनएक्स + dir[k, 0], ny + dir[k, 1]] 0 है, do -

      • एनएक्स:=एनएक्स + डीआईआर [के, 0]

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

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

      • अगर ठीक है (एनएक्स, एनवाई, होल [0], होल [1]), तो -

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

    • यदि विज़िट किया गया [nx, ny] शून्य है, तो −

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

  • वापसी "असंभव"

उदाहरण

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

#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