C++刷LeetCode（773. 滑动谜题）【广度优先搜索】
本帖最后由 糖逗 于 2021-1-15 13:29 编辑题目描述：
在一个 2 x 3 的板上（board）有 5 块砖瓦，用数字 1~5 来表示, 以及一块空缺用 0 来表示.
一次移动定义为选择 0 与一个相邻的数字（上下左右）进行交换.
最终当板 board 的结果是 [,] 谜板被解开。
给出一个谜板的初始状态，返回最少可以通过多少次移动解开谜板，如果不能解开谜板，则返回 -1 。
示例：
输入：board = [,]
输出：1
解释：交换 0 和 5 ，1 步完成
输入：board = [,]
输出：-1
解释：没有办法完成谜板
输入：board = [,]
输出：5
解释：
最少完成谜板的最少移动次数是 5 ，
一种移动路径:
尚未移动: [,]
移动 1 次: [,]
移动 2 次: [,]
移动 3 次: [,]
移动 4 次: [,]
移动 5 次: [,]
输入：board = [,]
输出：14
提示：
board 是一个如上所述的 2 x 3 的数组.
board 是一个 的排列.
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sliding-puzzle
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
public:
int slidingPuzzle(vector<vector<int>>& board) {
string start = "";
int len1 = board.size(), len2 = board.size();
for (int i = 0; i < len1; i++) {
for (int j = 0; j < len2; j++) {
start.push_back(board + '0');
}
}
/*
012
345
*/
string end = "123450";
vector<vector<int> >neighbors = {
{1, 3},
{0, 2, 4},
{1, 5},
{0, 4},
{1, 3, 5},
{2, 4}
};
//广度优先搜索
queue<string>store;
set<string>visit;
store.push(start);
visit.insert(start);
int res = 0;
while(!store.empty()){
int len = store.size();
for(int i = 0; i < len; i++){
string temp = store.front();
store.pop();
if(temp == end)return res;
//找到当前string中0的位置
int index;
for(index = 0; index < temp.size(); index++){
if(temp == '0')break;
}
//将当前0与其邻居交换
for(auto cha : neighbors){
string cur = temp;
swap(cur, cur);
if(visit.count(cur) == 0){
store.push(cur);
visit.insert(cur);
}
}
}
res++;
}
return -1;
}
};
参考链接：https://leetcode-cn.com/problems/sliding-puzzle/solution/bfskuang-jia-miao-sha-ge-chong-yi-zhi-you-xi-by-la/
页:
[1]