Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में भूलभुलैया में कॉर्नर सेल से मिडिल सेल तक के पथ खोजें


मान लीजिए हमारे पास संख्याओं से भरा एक वर्ग भूलभुलैया है; हमें कॉर्नर सेल से मिडिल सेल तक के सभी पथ खोजने हैं। यहां, हम 4 दिशाओं ऊपर, नीचे, दाएं और बाएं में एक सेल से ठीक n चरण आगे बढ़ेंगे जहां n उस सेल का मान है। इस प्रकार, हम एक सेल [i,j] से सेल [i+n,j], [i-n, j], [i, j+n], और [i, j-n] पर जा सकते हैं जहां n सेल [i, j] का मान है।

उदाहरण के लिए, यदि इनपुट इस तरह का है:

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

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

  • N := 9
  • is_ok() फंक्शन परिभाषित करें, जो विजिटेड पेयर्स का सेट और पेयर pt लेता है: pt के पहले और दूसरे तत्व 0 से N की रेंज में हों और pt विजिटेड में न हो तो true लौटाएं
  • dir_row := { -1, 1, 0, 0} ऐरे परिभाषित करें
  • dir_col := { 0, 0, -1, 1} ऐरे परिभाषित करें
  • row := { 0, 0, N - 1, N - 1} ऐरे परिभाषित करें
  • col := { 0, N - 1, 0, N - 1} ऐरे परिभाषित करें
  • solve() फंक्शन परिभाषित करें, जो भूलभुलैया, पथ, विजिटेड सेट, करंट पेयर लेता है:
    • यदि करंट के पहले और दूसरे N/2 के बराबर हैं, तो पथ प्रदर्शित करें और लौटें
    • i := 0 से 3 तक लूप करें:
      • n := भूलभुलैया[करंट.फर्स्ट][करंट.सेकंड]
      • x := करंट.फर्स्ट + dir_row[i] * n
      • y := करंट.सेकंड + dir_col[i] * n
      • नेक्स्ट := x, y का पेयर बनाएं
      • यदि is_ok(विजिटेड, नेक्स्ट): विजिटेड में नेक्स्ट डालें, पथ में नेक्स्ट डालें, solve() कॉल करें, पथ से अंतिम हटाएं, विजिटेड से नेक्स्ट हटाएं
  • मेन मेथड से:
    • विजिटेड नामक पेयर्स का एक सेट परिभाषित करें
    • i := 0 से 3 तक लूप करें:
      • x := row[i], y := col[i]
      • pt := (x, y) का पेयर बनाएं
      • pt को विजिटेड और पथ में डालें, solve() कॉल करें, पथ से अंतिम हटाएं, विजिटेड से pt हटाएं

उदाहरण (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

  1. C++ में भूलभुलैया समस्या का समाधान C++ में भूलभुलैया समस्या का समाधान

    समस्या विवरण मान लीजिए एक गेंद एक भूलभुलैया में है जिसमें खाली स्थान और दीवारें हैं। गेंद किसी भी दिशा में (ऊपर, नीचे, बाएं, दाएं) लुढ़ककर खाली रास्तों से गुजर सकती है, लेकिन यह तब तक नहीं रुकेगी जब तक यह दीवार से न टकरा जाए। जब गेंद रुकती है, तो यह अगली दिशा चुन सकती है। हमें गेंद की प्रारंभिक स्

  1. - C++ प्रोग्राम: एकल लिंक्ड लिस्ट का मध्य पुनरावर्ती रूप से ज्ञात करना

    मान लें हमारे पास संख्याओं की एक सूची है; हमारा कार्य पुनरावृत्ति का उपयोग करके लिंक्ड लिस्ट का मध्य ज्ञात करना है। इसलिए यदि सूची तत्व [12, 14, 18, 36, 96, 25, 62] हैं, तो मध्य तत्व 36 है। इस समस्या को हल करने के लिए, हम सूची में नोड्स की कुल संख्या को पुनरावर्ती तरीके से गिनेंगे और इसका आधा करेंग

  1. - C++ प्रोग्राम: एक्सेल कॉलम शीर्षक से कॉलम संख्या ज्ञात करना

    हम जानते हैं कि एक्सेल कॉलम संख्याएं वर्णमाला क्रम में होती हैं। यह A से शुरू होती है, और Z के बाद, यह AA, AB, से ZZ तक होगी, फिर फिर से AAA, AAB, से ZZZ और इसी तरह। इसलिए कॉलम 1 A है, कॉलम 27 Z है। यहां हम देखेंगे कि यदि कॉलम संख्या दी गई है तो कॉलम अक्षर कैसे प्राप्त करें। इसलिए यदि कॉलम संख्या 80