数据结构
网络
关系数据库管理系统
操作系统
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+ 次浏览
