Câu đố trượt trong C ++

Giả sử chúng ta có một bảng 2x3, có 5 ô được biểu thị bằng các số từ 1 đến 5 và ở đó có một ô trống được biểu thị bằng 0.

Ở đây, một nước đi có nghĩa là 0 và một số liền kề (trên cùng, dưới cùng, trái hoặc phải) và hoán đổi nó. Điều này sẽ được giải quyết khi các phần tử được sắp xếp theo cách này:[[1,2,3], [4,5,0]].

Chúng tôi có bảng câu đố; chúng ta phải tìm số lần di chuyển ít nhất cần thiết để trạng thái của bàn cờ được giải quyết. Nếu điều này không thể giải quyết được, hãy trả về -1.

Vì vậy, nếu đầu vào giống như [[1,2,3], [0,4,5]], thì đầu ra sẽ là 2, vì chúng ta phải hoán đổi [0,4], sau đó [0,5].

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

Xác định một hàm trượtPuzzle (), hàm này sẽ lấy bảng làm đầu vào
nếu bảng được sắp xếp hoàn hảo thì -
- trả về 0
Xác định một hàng đợi q của ma trận 2d
chèn bảng vào q
Xác định một tập hợp được truy cập cho ma trận 2d
chèn bảng vào đã thăm
để khởi tạo lvl:=1, khi không phải q trống, hãy cập nhật (tăng lvl lên 1), thực hiện -
- sz:=kích thước của q
- trong khi sz khác 0, giảm sz sau mỗi lần lặp, thực hiện -
  - Xác định một nút mảng 2D =phần tử phía trước của q
  - xóa phần tử khỏi q
  - dx:=-1, y:=-1
  - để khởi tạo i:=0, khi tôi
    - để khởi tạo j:=0, khi j
      - nếu nút [i, j] giống với 0, thì -
        
        x:=i
        
        y:=j
        
        Ra khỏi vòng lặp
  - để khởi tạo k:=0, khi k <4, cập nhật (tăng k lên 1), thực hiện -
  - nếu nx <0 hoặc ny <0 hoặc nx> =số hàng của bảng hoặc ny> =số cột của bảng thì -
    - Bỏ qua phần sau, chuyển sang phần tiếp theo
  - nút trao đổi [x, y] và nút [nx, ny]
  - nếu nút được truy cập, thì -
    - nút trao đổi [x, y] và nút [nx, ny]
    - Bỏ qua phần sau, chuyển sang phần tiếp theo
  - chèn nút vào đã truy cập
  - nếu nút là người sắp xếp hoàn hảo của bảng, thì -
    - trả về lvl
  - chèn nút vào q
  - nút trao đổi [x, y] và nút [nx, ny]
trả về -1

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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));
}

Đầu vào

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

Câu đố trượt trong C ++

Ví dụ

Đầu vào

Đầu ra