C++刷LeetCode（773. 滑动谜题）【广度优先搜索】

糖逗

题目描述：

在一个 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] 的排列.

来源：力扣（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[0].size();
        for (int i = 0; i < len1; i++) {
            for (int j = 0; j < len2; j++) {
                start.push_back(board[i][j] + '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[index] == '0')break;
                }
                //将当前0与其邻居交换
                for(auto cha : neighbors[index]){
                    string cur = temp;
                    swap(cur[index], cur[cha]);
                    if(visit.count(cur) == 0){
                        store.push(cur);
                        visit.insert(cur);
                    }
                }
            }
            res++;
        }
        return -1;
    }
};

参考链接：https://leetcode-cn.com/problems ... i-zhi-you-xi-by-la/