เส้นทางที่สั้นที่สุดในการรับคีย์ทั้งหมดใน 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

    • ถ้า grid[i, j] เหมือนกับ '@' แล้ว −

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

    • ถ้า grid[i, j]>='a' และ grid[i, j] <='f' แล้ว −

      • cnt :=สูงสุดของ cnt และ grid[i, j] - 'a' + 1

• กำหนดการเยี่ยมชมหนึ่งชุด

• req :=2^(cnt - 1)

• กำหนดหนึ่งคิว q ของอาร์เรย์

• แทรก start ลงใน q

• แทรกเริ่มต้นในการเยี่ยมชม

• ระดับ :=0

• ในขณะที่ (ไม่ใช่ q ว่างเปล่า) ทำ -

  • sz :=ขนาดของ q

  • ในขณะที่ sz ไม่ใช่ศูนย์ ให้ลด sz หลังจากการวนซ้ำแต่ละครั้ง ให้ทำ -

    • กำหนด array 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]

      • คีย์ :=prevKey

      • ถ้า nx>=0 และ ny>=0 และ nx

        • ถ้า grid[nx, ny] เหมือนกับ '#' แล้ว −

          • ละเว้นส่วนต่อไปนี้ ข้ามไปยังการทำซ้ำถัดไป

        • ถ้า grid[nx, ny]>='a' และ grid[nx, ny] <='f' แล้ว −

          • คีย์ :=คีย์ OR (2^(grid[nx, ny] - ASCII of 'a'))

        • ถ้า grid[nx, ny]>='A' และ grid[nx, ny] <='F' แล้ว -

          • ถ้า (ปุ่ม shift ไปทางขวา (grid[nx, ny] - ASCII ของ '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