मान लीजिए एक भूलभुलैया है जिसमें खाली स्थान और दीवारें हैं और उस भूलभुलैया में एक गेंद भी है। गेंद ऊपर (u), नीचे (d), बाएं (l) या दाएं (r) दिशाओं में लुढ़ककर खाली स्थानों से गुजर सकती है, लेकिन यह दीवार से टकराने तक लुढ़कती रहती है। जब गेंद रुकती है, तो यह अगली दिशा चुन सकती है। उस भूलभुलैया में एक छेद भी है। गेंद छेद में गिर जाएगी यदि यह छेद पर लुढ़कती है।
तो यदि हमारे पास गेंद की स्थिति, छेद की स्थिति और भूलभुलैया है, तो हमें यह पता लगाना होगा कि गेंद सबसे छोटी दूरी तय करके छेद में कैसे गिर सकती है। यहां दूरी को गेंद द्वारा शुरुआत (शामिल नहीं) से छेद (सम्मिलित) तक तय किए गए खाली स्थानों की संख्या से परिभाषित किया गया है।
चलती दिशाओं को 'u', 'd', 'l' और 'r' का उपयोग करके लौटाएं। चूंकि कई अलग-अलग सबसे छोटे तरीके हो सकते हैं, और आउटपुट लेक्सिकोग्राफिक रूप से सबसे छोटा तरीका होना चाहिए। यदि गेंद छेद तक नहीं पहुंच सकती, तो "impossible" प्रदर्शित करें।
यहां भूलभुलैया को एक बाइनरी मैट्रिक्स द्वारा दर्शाया गया है। 1 का अर्थ दीवार है और 0 का अर्थ खाली स्थान। गेंद और छेद के निर्देशांक पंक्ति और स्तंभ इंडेक्स द्वारा दर्शाए गए हैं।
तो, यदि इनपुट इस तरह है

तो आउटपुट 'lul' होगा क्योंकि बाएं चलें, फिर ऊपर फिर बाएं, एक अन्य परिणाम 'ul' हो सकता है, ऊपर फिर बाएं, दोनों की लंबाई 6 है, लेकिन यह 'lul' से लेक्सिकोग्राफिक रूप से छोटा नहीं है
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे −
Data नामक एक डेटा प्रकार परिभाषित करें, जो दूरी, एक स्ट्रिंग d और निर्देशांक x,y लेगा।
आकार 4 x 2 का एक ऐरे dir परिभाषित करें := {{1, 0}, {0, - 1}, {0, 1}, { - 1, 0}}
आकार 4 का एक ऐरे dirst परिभाषित करें := {'d', 'l', 'r', 'u'}
एक फ़ंक्शन ok() परिभाषित करें, जो x1, y1, x2, y2 लेगा,
true लौटाएं यदि x1, x2 के समान है AND y1, y2 के समान है
मुख्य विधि से निम्नलिखित करें −
n := भूलभुलैया का पंक्ति आकार
m := (यदि n शून्येतर है, तो भूलभुलैया का स्तंभ आकार, अन्यथा 0)
एक प्राथमिकता कतार pq परिभाषित करें
(0, ball[0], ball[1], "") के साथ नया डेटा pq में डालें
आकार n x m का एक 2D ऐरे visited परिभाषित करें
जब तक (pq खाली नहीं है), करें −
curr := pq का शीर्ष तत्व
x := curr.x
y := curr.y
dist := curr.dist
d := curr.d
यदि ok(x, y, hole[0], hole[1]), तो −
d लौटाएं
visited[x, y] := true
pq से तत्व हटाएं
k := 0 से आरंभ करें, जब k − 4, अद्यतन करें (k को 1 से बढ़ाएं), करें −
nx := x, ny := y
tempDist := 0
जब तक nx + dir[k, 0] < n और nx + dir[k, 0] >= 0 और ny + dir[k, 1] < m और ny + dir[k, 1] >= 0 और maze[nx + dir[k, 0], ny + dir[k, 1]] 0 है, करें −
nx := nx + dir[k, 0]
ny := ny + dir[k, 1]
(tempDist को 1 से बढ़ाएं)
यदि ok(nx, ny, hole[0], hole[1]), तो −
लूप से बाहर आएं
यदि visited[nx, ny] शून्य है, तो −
नया Data(dist + tempDist, nx, ny, d + dirst[k]) pq में डालें
"impossible" लौटाएं
उदाहरण
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें −
#include <bits/stdc++.h> using namespace std; int dir[4][2] = {{1, 0}, {0, -1}, {0, 1}, {-1, 0}}; char dirst[4] = {'d', 'l', 'r', 'u'}; class Solution { public: struct Data { int dist; string d; int x, y; Data(int a, int b, int c, string s) { d = s; dist = a; x = b; y = c; } }; struct Comparator { bool operator()(Data a, Data b) { return a.dist != b.dist ? !(a.dist < b.dist) : !(a.d < b.d); } }; bool ok(int x1, int y1, int x2, int y2) { return x1 == x2 && y1 == y2; } string findShortestWay(vector<vector<int>> &maze, vector<int>&ball, vector<int> &hole) { int n = maze.size(); int m = n ? maze[0].size() : 0; priority_queue<vector<Data>, vector<Data>, Comparator> pq; pq.push(Data(0, ball[0], ball[1], "")); vector<vector<bool>> visited(n, vector<bool>(m)); while (!pq.empty()) { Data curr = pq.top(); int x = curr.x; int y = curr.y; int dist = curr.dist; string d = curr.d; if (ok(x, y, hole[0], hole[1])) { return d; } visited[x][y] = true; pq.pop(); for (int k = 0; k < 4; k++) { int nx = x; int ny = y; int tempDist = 0; while (nx + dir[k][0] < n && nx + dir[k][0] >= 0 && ny + dir[k][1] < m && ny + dir[k][1] >= 0 && !maze[nx + dir[k][0]][ny + dir[k][1]]) { nx += dir[k][0]; ny += dir[k][1]; tempDist++; if (ok(nx, ny, hole[0], hole[1])) break; } if (!visited[nx][ny]) { pq.push(Data(dist + tempDist, nx, ny, d + dirst[k])); } } } return "impossible"; } }; main() { Solution ob; vector<vector<int>> v = { {0, 0, 0, 0, 0}, {1, 1, 0, 0, 1}, {0, 0, 0, 0, 0}, {0, 1, 0, 0, 1}, {0, 1, 0, 0, 0}}; vector<int> v1 = {4, 3}, v2 = {0, 1}; cout << (ob.findShortestWay(v, v1, v2)); }इनपुट
vector<vector<int>> v = {{0, 0, 0, 0, 0}, {1, 1, 0, 0, 1}, {0, 0, 0, 0, 0}, {0, 1, 0, 0, 1}, {0, 1, 0, 0, 0}}; vector<int> v1 = {4, 3}, v2 = {0, 1};आउटपुट
lul