मान लीजिए हमारे पास संख्याओं से भरा एक वर्ग भूलभुलैया है; हमें एक कोने वाली सेल से लेकर बीच वाली सेल तक के सभी रास्ते खोजने होंगे। यहाँ, हम सेल से ठीक n कदम ऊपर, नीचे, दाएँ और बाएँ 4 दिशाओं में आगे बढ़ेंगे जहाँ n सेल का मान है। इस प्रकार, हम सेल [i+n,j] से [i-n, j], [i, j+n], और [i, j-n] सेल [i,j] से जा सकते हैं जहां n सेल का मान है [ मैं, जे]।
तो, अगर इनपुट पसंद है
| 3 | 4 | 4 | 4 | 7 | 3 | 4 | 6 | 3 |
| 6 | 7 | 5 | 6 | 6 | 2 | 6 | 6 | 2 |
| 3 | 3 | 4 | 3 | 2 | 5 | 4 | 7 | 2 |
| 6 | 5 | 5 | 1 | 2 | 3 | 6 | 5 | 6 |
| 3 | 3 | 4 | 3 | 0 | 1 | 4 | 3 | 4 |
| 3 | 3 | 4 | 3 | 2 | 1 | 3 | 3 | 5 |
| 3 | 5 | 4 | 3 | 2 | 6 | 4 | 4 | 3 |
| 3 | 5 | 1 | 3 | 7 | 5 | 3 | 6 | 3 |
| 6 | 2 | 4 | 3 | 4 | 5 | 4 | 5 | 1 |
तो आउटपुट होगा
-
(0, 0)→(0, 3)→(0, 7)→(6, 7)→(6, 3)→(3, 3)→(3, 4)→(5, 4)→(5 , 2)→(1, 2)→(1, 7)→(7, 7)→(7, 1)→(2, 1)→(5, 1)→(0, 1)→(4, 1 )→(4, 4)→मध्य
-
(0, 0)→(0, 3)→(0, 7)→(6, 7)→(6, 3)→(3, 3)→(3, 4)→(5, 4)→(5 , 2)→(1, 2)→(1, 7)→(7, 7)→(7, 1)→(2, 1)→(2, 4)→(4, 4→मध्य
-
(0, 0)→(0, 3)→(0, 7)→(0, 1)→(4, 1)→(7, 1)→(2, 1)→(2, 4)→(4 , 4)→मध्य
-
(0, 0)→(0, 3)→(0, 7)→(0, 1)→(4, 1)→(4, 4)→मध्य
-
(8, 8)→(7, 8)→(4, 8)→(4, 4)→मध्य
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
एन:=9
-
फ़ंक्शन को परिभाषित करें is_ok(), इसमें जोड़े के एक सेट को विज़िट किया जाएगा, एक जोड़ी पीटी,
-
जब पीटी का पहला और दूसरा तत्व 0 से एन और पीटी के बीच में नहीं है, तो सही लौटें
-
एक सरणी परिभाषित करें dir_row :={ - 1, 1, 0, 0}
-
एक सरणी परिभाषित करें dir_col :={ 0, 0, - 1, 1}
-
एक सरणी पंक्ति को परिभाषित करें:={ 0, 0, N-1, N-1}
-
एक सरणी को परिभाषित करें :={ 0, N-1, 0, N-1}
-
एक फ़ंक्शन हल करें () को परिभाषित करें, यह भूलभुलैया, पथ, जोड़े का एक सेट, एक जोड़ी वक्र,
ले जाएगा -
यदि पहला और दूसरा curr N / 2 के समान है, तो -
-
पथ प्रदर्शित करें
-
वापसी
-
-
इनिशियलाइज़ करने के लिए मैं :=0, जब i <4, अपडेट (i 1 से बढ़ाएँ), करें -
-
n :=भूलभुलैया [curr.first, curr.second]
-
x :=curr.first + dir_row[i] * n
-
y :=curr.second + dir_col[i] * n
-
n :=x, y का उपयोग करने वाला एक जोड़ा
-
अगर is_ok(विज़िट किया गया, अगला), तो -
-
विज़िट किए गए में अगला डालें
-
पथ के अंत में अगला डालें
-
हल करें (भूलभुलैया, पथ, विज़िट किया गया, अगला)
-
पथ से अंतिम तत्व हटाएं
-
विज़िट में से अगला हटाएं
-
-
-
मुख्य विधि से, निम्न कार्य करें -
-
जोड़े के एक सेट को परिभाषित करें जिसे विज़िट किया गया कहा जाता है
-
इनिशियलाइज़ करने के लिए मैं :=0, जब i <4, अपडेट (i 1 से बढ़ाएँ), करें -
-
x:=पंक्ति[i]
-
वाई:=कर्नल [i]
-
pt :=(x, y) का उपयोग करके एक जोड़ी बनाएं
-
विज़िट किए गए में पीटी डालें
-
पथ के अंत में पीटी डालें
-
हल करें (भूलभुलैया, पथ, विज़िट किया गया, पीटी)
-
पथ से अंतिम तत्व हटाएं
-
देखे गए से पीटी हटाएं
-
उदाहरण (C++)
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
#include <bits/stdc++.h>
using namespace std;
#define N 9
bool is_ok(set<pair<int, int> > visited, pair<int, int> pt) {
return (pt.first >= 0) && (pt.first < N) && (pt.second >= 0) && (pt.second < N) && (visited.find(pt) == visited.end());
}
void display_path(list<pair<int, int> > path) {
for (auto it = path.begin(); it != path.end(); it++)
cout << "(" << it->first << ", " << it->second << ")->";
cout << "MIDDLE" << endl << endl;
}
int dir_row[] = {-1, 1, 0, 0};
int dir_col[] = { 0, 0, -1, 1};
int row[] = { 0, 0, N-1, N-1};
int col[] = { 0, N-1, 0, N-1};
void solve(int maze[N][N], list<pair<int, int> > &path, set<pair<int, int> > &visited, pair<int, int> &curr) {
if (curr.first == N / 2 && curr.second == N / 2) {
display_path(path);
return;
}
for (int i = 0; i < 4; ++i) {
int n = maze[curr.first][curr.second];
int x = curr.first + dir_row[i]*n;
int y = curr.second + dir_col[i]*n;
pair<int, int> next = make_pair(x, y);
if (is_ok(visited, next)) {
visited.insert(next);
path.push_back(next);
solve(maze, path, visited, next);
path.pop_back();
visited.erase(next);
}
}
}
void search_path(int maze[N][N]) {
list<pair<int, int> > path;
set<pair<int, int> > visited;
for (int i = 0; i < 4; ++i) {
int x = row[i];
int y = col[i];
pair<int, int> pt = make_pair(x, y);
visited.insert(pt);
path.push_back(pt);
solve(maze, path, visited, pt);
path.pop_back();
visited.erase(pt);
}
}
int main() {
int maze[N][N] = {
{3, 4, 4, 4, 7, 3, 4, 6, 3},
{6, 7, 5, 6, 6, 2, 6, 6, 2},
{3, 3, 4, 3, 2, 5, 4, 7, 2},
{6, 5, 5, 1, 2, 3, 6, 5, 6},
{3, 3, 4, 3, 0, 1, 4, 3, 4},
{3, 5, 4, 3, 2, 1, 3, 3, 5},
{3, 5, 4, 3, 2, 6, 4, 4, 3},
{3, 5, 1, 3, 7, 5, 3, 6, 3},
{6, 2, 4, 3, 4, 5, 4, 5, 1}
};
search_path(maze);
} इनपुट
{{3, 4, 4, 4, 7, 3, 4, 6, 3},
{6, 7, 5, 6, 6, 2, 6, 6, 2},
{3, 3, 4, 3, 2, 5, 4, 7, 2},
{6, 5, 5, 1, 2, 3, 6, 5, 6},
{3, 3, 4, 3, 0, 1, 4, 3, 4},
{3, 5, 4, 3, 2, 1, 3, 3, 5},
{3, 5, 4, 3, 2, 6, 4, 4, 3},
{3, 5, 1, 3, 7, 5, 3, 6, 3},
{6, 2, 4, 3, 4, 5, 4, 5, 1}} आउटपुट
(0, 0)->(0, 3)->(0, 7)->(6, 7)->(6, 3)->(3, 3)->(3, 4)->(5, 4)->(5, 2)->(1, 2)->(1, 7)->(7, 7)->(7, 1)->(2, 1)->(5, 1)->(0, 1)->(4, 1)->(4, 4)->MIDDLE (0, 0)->(0, 3)->(0, 7)->(6, 7)->(6, 3)->(3, 3)->(3, 4)->(5, 4)->(5, 2)->(1, 2)->(1, 7)->(7, 7)->(7, 1)->(2, 1)->(2, 4)->(4, 4)->MIDDLE (0, 0)->(0, 3)->(0, 7)->(0, 1)->(4, 1)->(7, 1)->(2, 1)->(2, 4)->(4, 4)->MIDDLE (0, 0)->(0, 3)->(0, 7)->(0, 1)->(4, 1)->(4, 4)->MIDDLE (8, 8)->(7, 8)->(4, 8)->(4, 4)->MIDDLE
