सी ++ में सभी कुंजी प्राप्त करने का सबसे छोटा रास्ता

मान लीजिए कि हमारे पास एक ग्रिड है। कुछ प्रतीक हैं। "।" खाली सेल का संकेत दे रहा है, "#" दीवार के लिए है, "@" शुरुआती बिंदु के लिए है, ("ए", "बी", ...) सभी कुंजियां हैं, और ("ए", "बी", ... ) सभी ताले हैं। हम शुरुआती बिंदु से शुरू करेंगे, और एक चाल में 4 दिशाओं (बाएं, दाएं, ऊपर, नीचे) में से एक में एक स्थान चलना शामिल है। हम ग्रिड से बाहर नहीं जाएंगे, और हमारे रास्ते को अवरुद्ध करने के लिए दीवारें हैं। यदि हम किसी चाबी के ऊपर से चलते हैं, तो हम उसे उठा लेते हैं। जब तक हमारे पास संबंधित कुंजी न हो, हम ताले के ऊपर से नहीं चल सकते।

ए, बी आदि जैसे प्रत्येक लॉक के लिए हमारे पास ए, बी, आदि जैसी चाबियां होती हैं, इसलिए लॉक अपरकेस अक्षरों में एक ही अक्षर होते हैं और चाबियां लोअर केस अक्षरों के साथ समान होती हैं।

हमें सभी कुंजियों को प्राप्त करने के लिए सबसे कम संख्या में चालों को खोजना होगा। अगर यह असंभव है, तो -1 लौटें।

इसलिए, यदि इनपुट ["@.a.#",,"###.#",,"b.A.B"] जैसा है, तो आउटपुट 8

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

• n :=पंक्तियों की संख्या, m :=स्तंभों की संख्या

• आकार 3 की एक सरणी प्रारंभ परिभाषित करें

• सीएनटी:=0

• इनिशियलाइज़ i :=0 के लिए, जब i

  • इनिशियलाइज़ j :=0 के लिए, जब j

    • अगर ग्रिड [i, j] '@' के समान है, तो -

      • प्रारंभ [1]:=मैं, प्रारंभ [2]:=जे

    • अगर ग्रिड[i, j]>='a' और ग्रिड[i, j] <='f', तो -

      • cnt :=अधिकतम cnt और ग्रिड[i, j] - 'a' + 1

• देखे गए एक सेट को परिभाषित करें

• अनुरोध :=2^(cnt - 1)

• सरणियों की एक कतार q परिभाषित करें

• q में प्रारंभ डालें

• विज़िट में प्रारंभ डालें

• स्तर:=0

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

  • sz :=q का आकार

  • जबकि sz गैर-शून्य है, प्रत्येक पुनरावृत्ति के बाद sz घटाएं, −

    . करें

    • एक सरणी को परिभाषित करें curr :=q का अगला तत्व

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

    • कुंजी:=वर्तमान [0]

    • यदि कुंजी req के समान है, तो -

      • वापसी स्तर

    • x :=curr[1], y :=curr[2]

    • prevKey :=key

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

      • एनएक्स:=एक्स + डीआईआर [i, 0], एनवाई:=वाई + डीआईआर [i, 1]

      • कुंजी :=पिछलाकुंजी

      • अगर nx>=0 और ny>=0 और nx

        • अगर ग्रिड [एनएक्स, एनवाई] '#' के समान है, तो -

          • निम्नलिखित भाग पर ध्यान न दें, अगले पुनरावृत्ति पर जाएं

        • अगर ग्रिड [एनएक्स, एनवाई]>='ए' और ग्रिड [एनएक्स, एनवाई] <='एफ', तो -

          • key :=key OR (2^(grid[nx, ny] - ASCII of 'a'))

        • अगर ग्रिड [एनएक्स, एनवाई]>='ए' और ग्रिड [एनएक्स, एनवाई] <='एफ', तो -

          • अगर (दाईं ओर शिफ्ट कुंजी (ग्रिड [एनएक्स, एनवाई] - 'ए' का एएससीआईआई) टाइम्स और 1 0 के समान है, तो -

            • निम्नलिखित भाग पर ध्यान न दें, अगले पुनरावृत्ति पर जाएं

        • एक सरणी स्थिति परिभाषित करें ({कुंजी, nx, ny})

        • यदि राज्य का दौरा किया गया है, तो -

          • निम्नलिखित भाग पर ध्यान न दें, अगले पुनरावृत्ति पर जाएं

        • q में राज्य डालें

        • विज़िट में राज्य डालें

  • (स्तर 1 से बढ़ाएँ)

• वापसी -1

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

उदाहरण

#include <bits/stdc++.h>
using namespace std;
int dir[4][2] = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}};
class Solution {
   public:
   int shortestPathAllKeys(vector<string>& grid) {
      int n = grid.size();
      int m = grid[0].size();
      vector<int> start(3);
      int cnt = 0;
      for (int i = 0; i < n; i++) {
         for (int j = 0; j < m; j++) {
            if (grid[i][j] == '@') {
               start[1] = i;
               start[2] = j;
            }
            if (grid[i][j] >= 'a' && grid[i][j] <= 'f') {
               cnt = max(cnt, grid[i][j] - 'a' + 1);
            }
         }
      }
      set<vector<int> > visited;
      int req = (1 << cnt) - 1;
      queue<vector<int> > q;
      q.push(start);
      visited.insert(start);
      int level = 0;
      while (!q.empty()) {
         int sz = q.size();
         while (sz--) {
            vector<int> curr = q.front();
            q.pop();
            int key = curr[0];
            if (key == req)
            return level;
            int x = curr[1];
            int y = curr[2];
            int nx, ny;
            int prevKey = key;
            for (int i = 0; i < 4; i++) {
               nx = x + dir[i][0];
               ny = y + dir[i][1];
               key = prevKey;
               if (nx >= 0 && ny >= 0 && nx < n && ny < m) {
                  if (grid[nx][ny] == '#')
                  continue;
                  if (grid[nx][ny] >= 'a' && grid[nx][ny] <=
                  'f') {
                     key |= (1 << (grid[nx][ny] - 'a'));
                  }
                  if (grid[nx][ny] >= 'A' && grid[nx][ny] <=
                  'F') {
                     if (((key >> (grid[nx][ny] - 'A')) & 1)
                     == 0)
                     continue;
                  }
                  vector<int> state({ key, nx, ny });
                  if (visited.count(state))
                  continue;
                  q.push(state);
                  visited.insert(state);
               }
            }
         }
         level++;
      }
      return -1;
   }
};
main(){
   Solution ob;
   vector<string> v = {"@.a.#","###.#","b.A.B"};
   cout << (ob.shortestPathAllKeys(v));
}

इनपुट

{"@.a.#","###.#","b.A.B"}

आउटपुट

8