Giả sử chúng ta có một bàn cờ 2x3, có 5 ô được biểu diễn bằng số 1 đến 5, và một ô trống được biểu diễn bằng 0.
Ở đây một nước đi nghĩa là hoán đổi 0 với một số liền kề (trên, dưới, trái hoặc phải). Trò chơi được coi là giải được khi các phần tử được sắp xếp theo cách này: [[1,2,3],[4,5,0]].
Chúng ta có bàn cờ của trò chơi; chúng ta phải tìm số nước đi ít nhất cần thiết để trạng thái bàn cờ được giải quyết. Nếu không thể giải, 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 bài toán này, chúng ta sẽ làm theo các bước sau −
Định nghĩa hàm slidingPuzzle(), nhận board làm đầu vào
nếu board đã sắp xếp đúng thì −
trả về 0
Định nghĩa một hàng đợi q của ma trận 2D
chèn board vào q
Định nghĩa một tập hợp visited cho ma trận 2D
chèn board vào visited
for khởi tạo lvl := 1, khi q không rỗng, cập nhật (tăng lvl lên 1), thực hiện −
sz := kích thước của q
khi sz khác 0, giảm sz sau mỗi lần lặp, thực hiện −
Định nghĩa một mảng 2D node = phần tử đầu của q
xóa phần tử khỏi q
dx := -1, y := -1
for khởi tạo i := 0, khi i < kích thước của board, cập nhật (tăng i lên 1), thực hiện −
for khởi tạo j := 0, khi j < kích thước của board[0], cập nhật (tăng j lên 1), thực hiện −
nếu node[i, j] bằng 0, thì −
x := i
y := j
Thoát khỏi vòng lặp
for 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 board hoặc ny >= số cột của board, thì −
Bỏ qua phần tiếp theo, chuyển sang vòng lặp tiếp theo
hoán đổi node[x, y] và node[nx, ny]
nếu node có trong visited, thì −
hoán đổi node[x, y] và node[nx, ny]
Bỏ qua phần tiếp theo, chuyển sang vòng lặp tiếp theo
chèn node vào visited
nếu node là sắp xếp hoàn hảo của bàn cờ, thì −
trả về lvl
chèn node vào q
hoán đổi node[x, y] và node[nx, ny]
trả về -1
Hãy xem 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}} Đầu ra
2