C++-এ সমস্ত কী পাওয়ার সংক্ষিপ্ত পথ

ধরুন আমাদের একটি গ্রিড আছে। কয়েকটি প্রতীক আছে। "" খালি ঘর নির্দেশ করছে, "#" হল প্রাচীরের জন্য, "@" হল প্রারম্ভিক বিন্দুর জন্য, ("a", "b", ...) সবগুলি কী, এবং ("A", "B", ... ) সবগুলোই তালা। আমরা প্রারম্ভিক বিন্দু থেকে শুরু করব, এবং একটি পদক্ষেপের মধ্যে 4টি দিকের (বাম, ডান, উপরে, নীচে) এক জায়গায় হাঁটা। আমরা গ্রিডের বাইরে যাব না, এবং আমাদের পথ আটকানোর জন্য দেয়াল রয়েছে। যদি আমরা একটি চাবির উপর দিয়ে হেঁটে যাই, আমরা তা তুলে নিই। আমাদের কাছে সংশ্লিষ্ট চাবি না থাকলে আমরা তালা দিয়ে হাঁটতে পারি না।

প্রতিটি লক যেমন A, B ইত্যাদির জন্য আমাদের কাছে a, b, ইত্যাদির মতো কী আছে, তাই লকগুলি বড় হাতের অক্ষরে একই অক্ষর এবং চাবিগুলি ছোট হাতের অক্ষরগুলির সাথে একই।

সমস্ত কীগুলি অর্জন করতে আমাদের সর্বনিম্ন সংখ্যক চাল খুঁজে বের করতে হবে। যদি এটি অসম্ভব হয়, -1 ফেরত দিন।

সুতরাং, যদি ইনপুট হয় ["@.a.#","###.#","b.A.B"], তাহলে আউটপুট হবে 8

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• n :=সারির সংখ্যা, m :=কলামের সংখ্যা

• আকার 3

  এর একটি অ্যারের শুরু সংজ্ঞায়িত করুন

• cnt :=0

• আরম্ভ করার জন্য i :=0, যখন i

  • j শুরু করার জন্য :=0, যখন j করুন

    • যদি গ্রিড[i, j] '@' এর মত হয়, তাহলে −

      • start[1] :=i, start[2] :=j

    • যদি গ্রিড[i, j]>='a' এবং grid[i, j] <='f' হয়, তাহলে −

      • cnt :=cnt এবং গ্রিডের সর্বাধিক [i, j] - 'a' + 1

• পরিদর্শন করা একটি সেট সংজ্ঞায়িত করুন

• req :=2^(cnt - 1)

• অ্যারের একটি সারি q সংজ্ঞায়িত করুন

• q

  -এ স্টার্ট সন্নিবেশ করান

• পরিদর্শন করা

  -এ সূচনা সন্নিবেশ করান

• স্তর :=0

• যখন (q খালি নয়), −

  করুন

  • sz :=q এর আকার

  • যখন sz অ-শূন্য, প্রতিটি পুনরাবৃত্তির পরে sz হ্রাস করুন, −

    করুন

    • একটি অ্যারে curr সংজ্ঞায়িত করুন :=q এর সামনের উপাদান

    • q

      থেকে উপাদান মুছুন

    • কী :=curr[0]

    • যদি কী req এর মত হয়, তাহলে −

      • রিটার্ন লেভেল

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

    • prevKey :=কী

    • আরম্ভ করার জন্য i :=0, যখন i <4, আপডেট করুন (i 1 দ্বারা বাড়ান), করবেন −

      • nx :=x + dir[i, 0], ny :=y + dir[i, 1]

      • key :=prevKey

      • যদি nx>=0 এবং ny>=0 এবং nx

        • যদি গ্রিড[nx, ny] '#' এর মত হয়, তাহলে −

          • নিম্নলিখিত অংশ উপেক্ষা করুন, পরবর্তী পুনরাবৃত্তি এড়িয়ে যান

        • যদি গ্রিড[nx, ny]>='a' এবং grid[nx, ny] <='f' হয়, তাহলে −

          • কী :=কী বা (2^(গ্রিড[nx, ny] - 'a'-এর ASCII))

        • যদি গ্রিড[nx, ny]>='A' এবং grid[nx, ny] <='F' হয়, তাহলে −

          • যদি (ডানদিকে শিফট কী (গ্রিড[nx, ny] - 'A'-এর ASCII) timesAND 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