C++ এ স্লাইডিং পাজল

ধরুন আমাদের একটি 2x3 বোর্ড আছে, সেখানে 5টি টাইল আছে যেগুলিকে 1 থেকে 5 নম্বর দ্বারা উপস্থাপন করা হয়েছে, এবং একটি খালি বর্গ আছে, যা 0 দ্বারা প্রতিনিধিত্ব করা হয়েছে৷

এখানে একটি সরানো মানে 0 এবং একটি সংলগ্ন সংখ্যা (উপর, নীচে, বাম বা ডান) এবং এটি অদলবদল করা। উপাদানগুলিকে এইভাবে সাজানো হলে এটি সমাধান করা হবে:[[1,2,3],[4,5,0]]।

আমরা ধাঁধা বোর্ড আছে; আমাদের সর্বনিম্ন সংখ্যক চাল খুঁজে বের করতে হবে যাতে বোর্ডের অবস্থা সমাধান করা হয়। যদি এটি সমাধান করা সম্ভব না হয়, তাহলে -1 ফেরত দিন।

সুতরাং, ইনপুট যদি [[1,2,3],[0,4,5]] এর মত হয়, তাহলে আউটপুট হবে 2, যেমন আমাদেরকে [0,4], তারপর [0,5] অদলবদল করতে হবে।

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

• একটি ফাংশন slidingPuzzle(), এটি বোর্ডকে ইনপুট হিসাবে গ্রহণ করবে

• যদি বোর্ডটি পুরোপুরি সাজানো থাকে তাহলে −

  • রিটার্ন 0

• 2d ম্যাট্রিক্সের একটি সারি q সংজ্ঞায়িত করুন

• q

  -এ বোর্ড সন্নিবেশ করান

• 2d ম্যাট্রিক্সের জন্য পরিদর্শন করা একটি সেট সংজ্ঞায়িত করুন

• পরিদর্শন

  এ বোর্ড সন্নিবেশ করান

• lvl শুরু করার জন্য :=1, যখন q খালি না থাকে, আপডেট করুন (lvl 1 দ্বারা বাড়ান), করুন −

  • sz :=q এর আকার

  • যখন sz অ-শূন্য, প্রতিটি পুনরাবৃত্তির পরে sz হ্রাস করুন, −

    করুন

    • একটি 2D অ্যারে নোড =q এর সামনের উপাদান

      সংজ্ঞায়িত করুন

    • q

      থেকে উপাদান মুছুন

    • dx :=-1, y :=-1

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

      • j শুরু করার জন্য :=0, যখন j <বোর্ডের আকার[0], আপডেট করুন (j 1 দ্বারা বৃদ্ধি করুন), করুন −

        • যদি নোড[i, j] 0 এর মত হয়, তাহলে −

          • x :=i

          • y :=j

          • লুপ থেকে বেরিয়ে আসুন

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

    • যদি nx <0 বা ny <0 বা nx>=বোর্ডের সারি গণনা বা ny>=বোর্ডের কলাম সংখ্যা, তাহলে −

      • নিম্নলিখিত অংশ উপেক্ষা করুন, পরবর্তী পুনরাবৃত্তি এড়িয়ে যান

    • বিনিময় নোড[x, y] এবং নোড[nx, ny]

    • যদি নোড পরিদর্শন করা হয়, তাহলে -

      • বিনিময় নোড[x, y] এবং নোড[nx, ny]

      • নিম্নলিখিত অংশ উপেক্ষা করুন, পরবর্তী পুনরাবৃত্তি এড়িয়ে যান

    • ভিজিটেড

      -এ নোড সন্নিবেশ করান

    • যদি নোডটি বোর্ডের নিখুঁত সাজানো হয়, তাহলে -

      • ফিরুন lvl

    • q

      -এ নোড সন্নিবেশ করান

    • বিনিময় নোড[x, y] এবং নোড[nx, ny]

• রিটার্ন -1

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

#include <bits/stdc++.h>
using namespace std;
int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
class Solution {
   public:
   bool ok(vector < vector <int> >& b){
      return b[0][0] == 1 && b[0][1] == 2 && b[0][2] == 3 && b[1]
      [0] == 4 && b[1][1] == 5;
   }
   int slidingPuzzle(vector<vector<int>>& board) {
      if (ok(board))
      return 0;
      queue<vector<vector<int> > > q;
      q.push(board);
      set<vector<vector<int> > > visited;
      visited.insert(board);
      for (int lvl = 1; !q.empty(); lvl++) {
         int sz = q.size();
         while (sz--) {
            vector<vector<int> > node = q.front();
            q.pop();
            int x = -1;
            int y = -1;
            for (int i = 0; i < board.size(); i++) {
               for (int j = 0; j < board[0].size(); j++) {
                  if (node[i][j] == 0) {
                     x = i;
                     y = j;
                     break;
                  }
               }
            }
            for (int k = 0; k < 4; k++) {
               int nx = x + dir[k][0];
               int ny = y + dir[k][1];
               if (nx < 0 || ny < 0 || nx >= board.size() || ny
               >= board[0].size())
               continue;
               swap(node[x][y], node[nx][ny]);
               if (visited.count(node)) {
                  swap(node[x][y], node[nx][ny]);
                  continue;
               }
               visited.insert(node);
               if (ok(node))
               return lvl;
               q.push(node);
               swap(node[x][y], node[nx][ny]);
            }
         }
      }
      return -1;
   }
};
main(){
   Solution ob;
   vector<vector<int>> v = {{1,2,3},{0,4,5}};
   cout << (ob.slidingPuzzle(v));
}

ইনপুট

{{1,2,3},{0,4,5}}

আউটপুট

2