ปริศนาสไลด์ใน C++

สมมติว่าเรามีกระดาน 2x3 มีกระเบื้อง 5 ชิ้น แทนด้วยตัวเลข 1-5 และช่องว่าง 1 ชิ้น แทนด้วย 0

การเคลื่อนที่คือการสลับ 0 กับตัวเลขที่ติดกัน (บน, ล่าง, ซ้าย, ขวา) จะถือว่าแก้เสร็จเมื่อเรียงเป็น [[1,2,3],[4,5,0]]

ให้กระดานปริศนา เราต้องหาจำนวนการเคลื่อนที่น้อยที่สุดเพื่อแก้ปริศนา หากแก้ไม่ได้คืน -1

เช่น [[1,2,3],[0,4,5]] เอาต์พุตคือ 2 สลับ [0,4] แล้ว [0,5]

วิธีแก้ − ใช้ BFS ค้นหาสถานะทั้งหมด ตรวจสอบสถานะเป้าหมาย

ตัวอย่าง

#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, 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], 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