C++でのスライディングパズル

2x3のボードが1つあり、1から5までの数字で表されるタイルが5つあり、0で表される空の正方形が1つあるとします。

ここでの移動とは、0と1つの隣接する番号（上、下、左、または右）とそれを交換することを意味します。これは、要素が[[1,2,3]、[4,5,0]]のように配置されている場合に解決されます。

パズルボードがあります。ボードの状態を解決するために必要な最小の移動数を見つける必要があります。これを解決できない場合は、-1を返します。

したがって、入力が[[1,2,3]、[0,4,5]]の場合、[0,4]、次に[0,5]を交換する必要があるため、出力は2になります。

これを解決するには、次の手順に従います-

• 1つの関数slidingPuzzle（）を定義します。これは、ボードを入力として受け取ります

• ボードが完全に配置されている場合-

  • 0を返す

• 2次元行列の1つのキューqを定義します

• ボードをqに挿入

• 2次元行列のために訪問した1つのセットを定義します

• 訪問したボードにボードを挿入

• 初期化レベル：=1の場合、qが空でない場合は、更新（レベルを1増やします）、実行-

  • sz：=qのサイズ

  • szがゼロ以外の場合、各反復後にszを減らし、-

    を実行します。

    • 1つの2D配列ノード=qのフロント要素を定義します

    • qから要素を削除

    • dx：=-1、y：=-1

    • 初期化i：=0の場合、i <ボードのサイズの場合、更新（iを1増やします）、実行-

      • 初期化j：=0の場合、j <ボードのサイズ[0]の場合、更新（jを1増やします）、実行-

        • node [i、j]が0と同じ場合、-

          • x：=i

          • y：=j

          • ループから出てきます

    • 初期化k：=0の場合、k <4の場合、更新（kを1増やします）、実行-

    • nx<0またはny<0またはnx>=ボードの行数、またはny> =ボードの列数の場合、-

      • 次の部分を無視し、次の反復にスキップします

    • node [x、y]とnode [nx、ny]

      を交換します

    • ノードが訪問中の場合、-

      • node [x、y]とnode [nx、ny]

        を交換します

      • 次の部分を無視し、次の反復にスキップします

    • 訪問先にノードを挿入

    • ノードがボードの完璧な配置である場合、-

      • レベルを返す

    • qにノードを挿入

    • node [x、y]とnode [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