मान लीजिए हमारे पास एक ग्रिड है। कुछ प्रतीक हैं। "." खाली सेल दर्शाता है, "#" दीवार के लिए है, "@" प्रारंभिक बिंदु के लिए है, ("a", "b", ...) सभी कुंजियां हैं, और ("A", "B", ...) सभी ताले हैं। हम प्रारंभिक बिंदु से शुरू करेंगे, और एक चाल में 4 दिशाओं (बाएं, दाएं, ऊपर, नीचे) में से एक में एक स्थान चलना शामिल है। हम ग्रिड के बाहर नहीं जाएंगे, और दीवारें हमारे रास्ते को रोकती हैं। यदि हम कुंजी पर चलते हैं, तो हम उसे उठा लेते हैं। हम संबंधित कुंजी के बिना ताले पर नहीं चल सकते।
प्रत्येक ताले जैसे A, B आदि के लिए हमारे पास कुंजियां जैसे a, b, आदि होती हैं, इसलिए ताले बड़े अक्षरों में समान अक्षर हैं और कुंजियां लोअरकेस में समान हैं।
हमें सभी कुंजियों को प्राप्त करने के लिए चालों की न्यूनतम संख्या ज्ञात करनी है। यदि यह असंभव है, तो -1 लौटाएं।
यदि इनपुट ["@.a.#","###.#","b.A.B"] है, तो आउटपुट 8 होगा।
हल करने के चरण
n := पंक्तियों की संख्या, m := स्तंभों की संख्या
आकार 3 की सरणी start परिभाषित करें
cnt := 0
ग्रिड को पार करके प्रारंभिक स्थिति ढूंढें और कुंजियों की गिनती करें (cnt = अधिकतम कुंजी इंडेक्स + 1)
एक सेट visited परिभाषित करें
req := 2^cnt - 1 (सभी कुंजियों के लिए बिटमास्क)
सरणियों की एक कतार q परिभाषित करें, start को q और visited में डालें
level := 0
जब तक कतार खाली नहीं: प्रत्येक स्तर के लिए, वर्तमान स्थिति निकालें, यदि key == req तो level लौटाएं
चार दिशाओं में जाएं: दीवार छोड़ें, कुंजी उठाएं (बिटमास्क अपडेट करें), ताला जांचें (संबंधित कुंजी है या नहीं), नई स्थिति को visited में नहीं है तो कतार में डालें
level बढ़ाएं
यदि कतार खाली हो जाए तो -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;
}
};
int main() {
Solution ob;
vector<string> v = {"@.a.#","###.#","b.A.B"};
cout << (ob.shortestPathAllKeys(v));
return 0;
}
इनपुट
{"@.a.#","###.#","b.A.B"}
आउटपुट
8
