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]।

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

• एक फ़ंक्शन स्लाइडिंगपज़ल () को परिभाषित करें, यह इनपुट के रूप में बोर्ड लेगा

• अगर बोर्ड पूरी तरह से व्यवस्थित है तो -

  • वापसी 0

• 2d मैट्रिक्स की एक कतार q परिभाषित करें

• क्यू में बोर्ड डालें

• 2d मैट्रिसेस के लिए विज़िट किए गए एक सेट को परिभाषित करें

• विज़िट किए गए में बोर्ड डालें

• lvl को इनिशियलाइज़ करने के लिए:=1, जब q खाली न हो, तो अपडेट करें (lvl को 1 से बढ़ाएँ), करें -

  • sz :=q का आकार

  • जबकि sz गैर-शून्य है, प्रत्येक पुनरावृत्ति के बाद sz घटाएं, −

    . करें

    • एक 2D सरणी नोड परिभाषित करें =q का अगला तत्व

    • q से तत्व हटाएं

    • डीएक्स:=-1, वाई:=-1

    • इनिशियलाइज़ करने के लिए:=0, जब मैं <बोर्ड का आकार, अपडेट (i से 1 बढ़ाएँ), करें -

      • इनिशियलाइज़ j :=0 के लिए, जब j <बोर्ड का आकार [0], अपडेट करें (1 से j बढ़ाएँ), करें -

        • यदि नोड [i, j] 0 के समान है, तो -

          • एक्स:=मैं

          • वाई:=जे

          • लूप से बाहर आएं

    • इनिशियलाइज़ k :=0 के लिए, जब k <4, अपडेट करें (1 से k बढ़ाएँ), करें -

    • यदि nx <0 या ny <0 या nx>=बोर्ड की पंक्ति संख्या या ny>=बोर्ड की स्तंभ संख्या, तो -

      • निम्नलिखित भाग पर ध्यान न दें, अगले पुनरावृत्ति पर जाएं

    • एक्सचेंज नोड [x, y] और नोड [nx, ny]

    • यदि नोड का दौरा किया जाता है, तो -

      • एक्सचेंज नोड [x, y] और नोड [nx, ny]

      • निम्नलिखित भाग पर ध्यान न दें, अगले पुनरावृत्ति पर जाएं

    • देखे गए में नोड डालें

    • यदि नोड बोर्डों की सही व्यवस्था है, तो -

      • वापसी एलवीएल

    • क्यू में नोड डालें

    • एक्सचेंज नोड [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