資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究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
將棋盤插入 q
定義一個二維矩陣集合 visited
將棋盤插入 visited
初始化 lvl := 1，當 q 不為空時，更新（將 lvl 增加 1），執行：
sz := q 的大小
當 sz 不為零時，每次迭代後減少 sz，執行：
定義一個二維陣列 node = q 的首元素
從 q 中刪除元素
dx := -1, y := -1
初始化 i := 0，當 i < 棋盤的大小，更新（將 i 增加 1），執行：
初始化 j := 0，當 j < board[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 在 visited 中，則：
交換 node[x, y] 和 node[nx, ny]
忽略以下部分，跳過到下一次迭代
將 node 插入 visited
如果 node 是棋盤的完美排列，則：
返回 lvl
將 node 插入 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
1K+ 次瀏覽
