题目描述
在一个 2 x 3 的板 board
上有 5 块砖瓦,用数字 1~5
来表示, 以及一块空缺用 0
来表示.
一次移动定义为选择 0
与一个相邻的数字(上下左右)进行交换.
最终当板 board
的结果是 [[1,2,3],[4,5,0]]
谜板被解开。
给出一个谜板的初始状态,返回最少可以通过多少次移动解开谜板,如果不能解开谜板,则返回 -1。
样例
输入:board = [[1,2,3],[4,0,5]]
输出:1
解释:交换 0 和 5 ,1 步完成
输入:board = [[1,2,3],[5,4,0]]
输出:-1
解释:没有办法完成谜板
输入:board = [[4,1,2],[5,0,3]]
输出:5
解释:
最少完成谜板的最少移动次数是 5 ,
一种移动路径:
尚未移动: [[4,1,2],[5,0,3]]
移动 1 次: [[4,1,2],[0,5,3]]
移动 2 次: [[0,1,2],[4,5,3]]
移动 3 次: [[1,0,2],[4,5,3]]
移动 4 次: [[1,2,0],[4,5,3]]
移动 5 次: [[1,2,3],[4,5,0]]
输入:board = [[3,2,4],[1,5,0]]
输出:14
提示
board
是一个如上所述的 2 x 3 的数组。board[i][j]
是一个[0, 1, 2, 3, 4, 5]
的排列。
算法
(宽度优先搜素)
- 此题要求最少的移动次数,故可以采用宽度有限搜索。
- 这里需要将状态进行编码和解码,这里为了方便可以采用 6 进制的方式进行编码(也可以采用全排列进行编码,实现会比较复杂),即当前的状态表示为一个 6 位的 6 进制数字。
- 宽搜过程中进行编码和解码,如果遇到了最终状态则可以返回。
时间复杂度
- 和状态数一致,如果采用全排列的方式进行编码,则最坏的时间复杂度为 $6!$。
空间复杂度
- 和状态数一致。
C++ 代码
class Solution {
public:
int encode(const vector<vector<int>>& board) {
int t = 0;
for (int i = 0; i < 2; i++)
for (int j = 0; j < 3; j++)
t = t * 6 + board[i][j];
return t;
}
void decode(int t, vector<vector<int>> &board) {
board.resize(2, vector<int>(3));
for (int i = 1; i >= 0; i--)
for (int j = 2; j >= 0; j--) {
board[i][j] = t % 6;
t /= 6;
}
}
int slidingPuzzle(vector<vector<int>>& board) {
const int N = 50000;
const int dx[4] = {0, 1, 0, -1};
const int dy[4] = {1, 0, -1, 0};
vector<int> dis(N, -1);
queue<int> q;
const int S = encode(board);
const int T = 11190;
dis[S] = 0;
q.push(S);
while (!q.empty()) {
int u = q.front();
q.pop();
if (u == T) break;
vector<vector<int>> cur;
decode(u, cur);
for (int i = 0; i < 2; i++)
for (int j = 0; j < 3; j++)
if (cur[i][j] == 0) {
for (int k = 0; k < 4; k++) {
int x = i + dx[k], y = j + dy[k];
if (x < 0 || x >= 2 || y < 0 || y >= 3)
continue;
swap(cur[i][j], cur[x][y]);
int t = encode(cur);
if (dis[t] == -1) {
dis[t] = dis[u] + 1;
q.push(t);
}
swap(cur[i][j], cur[x][y]);
}
break;
}
}
return dis[T];
}
};