C++ এ গোলকধাঁধায় কর্নার সেল থেকে মিডল সেল পর্যন্ত পাথ খুঁজুন

ধরুন আমাদের কাছে সংখ্যায় ভরা একটি বর্গাকার গোলকধাঁধা আছে; আমাদের একটি কোণার কোষ থেকে মধ্য কক্ষে সমস্ত পথ খুঁজে বের করতে হবে। এখানে, আমরা একটি সেল থেকে উপরে, নিচে, ডান এবং বামে ৪টি দিক থেকে ঠিক n ধাপে এগিয়ে যাব যেখানে n হল ঘরের মান। এইভাবে, আমরা একটি সেল [i,j] থেকে [i+n,j] থেকে [i-n, j], [i, j+n], এবং [i, j-n] এ যেতে পারি যেখানে n হল ঘরের মান i, j]।

সুতরাং, যদি ইনপুট মত হয়

তাহলে আউটপুট হবে

• (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→Middle

• (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)→MIDDLE

• (8, 8)→(7, 8)→(4, 8)→(4, 4)→MIDDLE

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• N :=9

• একটি ফাংশন is_ok() সংজ্ঞায়িত করুন, এটি এক সেট জোড়া লাগবে যাকে পরিদর্শন বলা হয়, এক জোড়া pt,

• 0 থেকে N এবং pt পরিসরে pt-এর প্রথম এবং দ্বিতীয় উপাদান পরিদর্শনে না থাকলে সত্য ফেরত দিন

• একটি অ্যারে 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,

• যদি curr-এর প্রথম এবং দ্বিতীয়টি N/2 এর মত হয়, তাহলে −

  • পথ প্রদর্শন করুন

  • ফেরত

• আরম্ভ করার জন্য i :=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(পরিদর্শন করা হয়েছে, পরবর্তী), তারপর -

    • পরিদর্শন

      -এ পরবর্তী সন্নিবেশ করান

    • পথের শেষে পরবর্তী সন্নিবেশ করুন

    • সমাধান (ধাঁধা, পথ, পরিদর্শন করা, পরবর্তী)

    • পাথ থেকে শেষ উপাদান মুছুন

    • পরিদর্শন থেকে পরবর্তী মুছুন

• প্রধান পদ্ধতি থেকে, নিম্নলিখিতগুলি করুন -

• ভিজিটড

  বলে জোড়ার এক সেট সংজ্ঞায়িত করুন

• আরম্ভ করার জন্য i :=0, যখন i <4, আপডেট করুন (i 1 দ্বারা বাড়ান), করবেন −

  • x :=সারি [i]

  • y :=col[i]

  • pt :=(x, y)

    ব্যবহার করে একটি জোড়া তৈরি করুন

  • ভিজিট করা

    -এ pt ঢোকান

  • পাথের শেষে pt ঢোকান

  • সমাধান (ধাঁধা, পথ, পরিদর্শন করা, পিটি)

  • পাথ থেকে শেষ উপাদান মুছুন

  • পরিদর্শন থেকে 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