সি++-এ সব চাবি পেতে সবচেয়ে ছোট পথ

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

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

আমাদের সব চাবি পাওয়ার জন্য ন্যূনতম মুভের সংখ্যা বের করতে হবে। যদি অসম্ভব হয়, তবে -1 ফেরত দিন।

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

समाधान पद्धति

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

• n := সারি সংখ্যা, m := কলাম সংখ্যা
• আকার 3-এর একটি start সরণি সংজ্ঞায়িত করুন
• cnt := 0
• i := 0 থেকে आरंभ করুন, जब i < n, আপডেট করুন (i 1 বাড়ান), করুন:
  • j := 0 থেকে आरंभ করুন, जब j < m, আপডেট করুন (j 1 বাড়ান), করুন:
    • যদি grid[i, j] '@'-এর সমান হয়, তবে:
      • start[1] := i, start[2] := j
    • যদি grid[i, j] >= 'a' এবং grid[i, j] <= 'f', তবে:
      • cnt := cnt এবং grid[i, j] - 'a' + 1-এর সর্বোচ্চ
• একটি visited সেট সংজ্ঞায়িত করুন
• req := 2^(cnt - 1)
• সরণির একটি q কিউ সংজ্ঞায়িত করুন
• start কে q-তে ইনসার্ট করুন
• start কে visited-এ ইনসার্ট করুন
• level := 0
• যতক্ষণ (q খালি নয়), করুন:
  • sz := q-এর আকার
  • যতক্ষণ sz নন-জিরো, প্রতিটি ইটারেশনে sz কমান, করুন:
    • curr := q-এর ফ্রন্ট এলিমেন্ট সংজ্ঞায়িত করুন
    • q থেকে উপাদান মুছুন
    • key := curr[0]
    • যদি key, req-এর সমান হয়, তবে:
      • level ফেরত দিন
    • x := curr[1], y := curr[2]
    • prevKey := key
    • i := 0 থেকে आरंभ করুন, जब i < 4, আপডেট করুন (i 1 বাড়ান), করুন:
      • nx := x + dir[i, 0], ny := y + dir[i, 1]
      • key := prevKey
      • যদি nx >= 0 এবং ny >= 0 এবং nx < n এবং ny < m, তবে:
        • যদি grid[nx, ny] '#'-এর সমান হয়, তবে:
          • পরবর্তী অংশ বাদ দিন, পরবর্তী ইটারেশনে যান
        • যদি grid[nx, ny] >= 'a' এবং grid[nx, ny] <= 'f', তবে:
          • key := key OR (2^(grid[nx, ny] - 'a'-র ASCII))
        • যদি grid[nx, ny] >= 'A' এবং grid[nx, ny] <= 'F', তবে:
          • যদি (key কে (grid[nx, ny] - 'A'-র ASCII) বার রাইট শিফ্ট করলে AND 1) 0-এর সমান হয়, তবে:
            • পরবর্তী অংশ বাদ দিন, পরবর্তী ইটেরেশনে যান
        • state সরণি সংজ্ঞায়িত করুন ({ key, nx, ny })
        • যদি state visited-এ থাকে, তবে:
          • পরবর্তী অংশ বাদ দিন, পরবর্তী ইটেরেশনে যান
        • state কে q-তে ইনসার্ট করুন
        • state কে visited-এ ইনসার্ট করুন
    • (level 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