ปริศนาเลื่อนใน 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

• กำหนดหนึ่งคิว q ของเมทริกซ์ 2d

• ใส่บอร์ดลงใน q

• กำหนดหนึ่งชุดที่เข้าชมสำหรับเมทริกซ์ 2 มิติ

• ใส่บอร์ดเข้าไป

• สำหรับการเริ่มต้น lvl :=1 เมื่อไม่มี q ว่าง ให้อัปเดต (เพิ่ม lvl ขึ้น 1) ทำ -

  • sz :=ขนาดของ q

  • ในขณะที่ sz ไม่ใช่ศูนย์ ให้ลด sz หลังจากการวนซ้ำแต่ละครั้ง ให้ทำ -

    • กำหนดโหนดอาร์เรย์ 2 มิติหนึ่งโหนด =องค์ประกอบด้านหน้าของ q

    • ลบองค์ประกอบออกจาก q

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

    • สำหรับการเริ่มต้น i :=0 เมื่อ i <ขนาดของบอร์ด ให้อัปเดต (เพิ่ม i ขึ้น 1) ให้ทำ −

      • สำหรับการเริ่มต้น j :=0 เมื่อ j

        • ถ้าโหนด[i, j] เหมือนกับ 0 แล้ว −

          • x :=ผม

          • y :=เจ

          • ออกจากวง

    • สำหรับการเริ่มต้น k :=0 เมื่อ k <4 อัปเดต (เพิ่ม k ขึ้น 1) ทำ -

    • ถ้า nx <0 หรือ ny <0 หรือ nx>=จำนวนแถวของบอร์ดหรือ ny>=จำนวนคอลัมน์ของบอร์ด −

      • ละเว้นส่วนต่อไปนี้ ข้ามไปยังการทำซ้ำถัดไป

    • โหนดแลกเปลี่ยน[x, y] และโหนด[nx, ny]

    • ถ้าโหนดถูกเยี่ยมชม −

      • โหนดแลกเปลี่ยน[x, y] และโหนด[nx, ny]

      • ละเว้นส่วนต่อไปนี้ ข้ามไปยังการทำซ้ำถัดไป

    • แทรกโหนดเข้าเยี่ยมชม

    • ถ้าโหนดเป็นตัวจัดเรียงบอร์ดที่สมบูรณ์แบบ −

      • กลับเลเวล

    • แทรกโหนดลงใน 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