力扣773：滑动谜题

力扣773：滑动谜题

https://leetcode.cn/problems/sliding-puzzle/description/

代码内容：

class Solution {
public:
    int slidingPuzzle(vector<vector<int>>& board) {
        string start="";
        for(int i = 0;i<2;i++)
        {
            for(int j = 0;j<3;j++)
            {
                start.push_back(board[i][j]+'0');
            }
        }
        string target = "123450";
        //将二维数组压缩为一维数组的索引，以0所在位置
        vector<vector<int>> index{
            {1,3},
            {0,4,2},
            {1,5},
            {0,4},
            {3,1,5},
            {4,2}
        };
        //BFS
        queue<string> q;
        q.push(start);
        unordered_set<string> visited;
        visited.insert(start);

        int step = 0;
        while(!q.empty())
        {
            int size = q.size();
            for(int i = 0;i<size;i++)
            {
                string cur = q.front();
                q.pop();
                //如果这个是目标值，直接返回
                if(cur == target)
                    return step;
            
            
                //如果不是，查找对应的索引
                int ind;
                 for(ind = 0;cur[ind]!='0';ind++);
                 //查到0的位置，后根据位置进行各个方向交换
                for(int a:index[ind])
                {
                    string new_board = cur;
                    swap(new_board[ind],new_board[a]);
                    //防止重复，缩小时间复杂度
                    if(!visited.count(new_board))
                    {
                        q.push(new_board);
                        visited.insert(new_board);
                    }
                }
            }
            step++;
        }
        return -1;
    }
    
};

在一个 2 x 3 的板上（board）有 5 块砖瓦，用数字 1~5 来表示, 以及一块空缺用 0 来表示。一次 移动 定义为选择 0 与一个相邻的数字（上下左右）进行交换.

最终当板 board 的结果是 [[1,2,3],[4,5,0]] 谜板被解开。

给出一个谜板的初始状态 board ，返回最少可以通过多少次移动解开谜板，如果不能解开谜板，则返回 -1 。

这个题目主要就是暴力穷举的做法，将二维数组压缩为一维数组，用广度优先：

我们首先创建两个string类型，保存target和start,而我们的二维数组是int类型，所以我们需要先转换为string,通过将int+'0'来将数字转换为对应的字符.还有一个难点就是将二维数组压缩为一维数组后，一维数组怎么表示二维数组，我们这里使用了一个索引

vector<vector<int>> index{ {1,3}, {0,4,2}, {1,5}, {0,4}, {3,1,5}, {4,2} };

这个索引，主要表示'0'在6个不同位置，他可能交换的地方。例如：012345对应的下标为012345,即

我们此时的'0'在一维数组的0号下标,因此，我们进行交换可以向右交换，向下交换，即交换的索引就是1,3;

然后我们通过string类型的队列，一个一个广度搜索比较.