941 · 滑动拼图

在一块大小为 2x3 的板上，有 5 块瓦片，分别用整数 1 到 5 表示，还有一块空地用 0 表示。

一次移动表示 0 与其相邻的四个方向之一的数字交换位置。

当且仅当 这块板 上的瓦片摆放状态为 [[1,2,3],[4,5,0]] 时，才能说这块板存在的问题被解决了。

给定一个拼图板，返回所需的最少移动次数，以解决该板的状态。如果无法解决板的状态，则返回-1。

• board 会以上面讲的 2 x 3 大小的数组形式输入 。
• board[i][j] 会是 [0, 1, 2, 3, 4, 5] 中的其中一个值.

样例

样例 1:

给出 board = `[[1,2,3],[4,0,5]]`, 返回 `1`.

解释: 
交换0和5，只需要一步.

样例 2:

给出 board = `[[1,2,3],[5,4,0]]`, 返回 `-1`.

解释: 
不管移动多少步都无法解决问题。

样例 3:

给出 board = `[[4,1,2],[5,0,3]]`, 返回 `5`.

解释: 
至少需要移动5步来解决这个问题。
比如这么做:
移动 0 步之后: [[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]]

样例 4:

给出 board = `[[3,2,4],[1,5,0]]`, 返回 `14`.

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

string NumberToString(int x) {
    stringstream ss;
    ss << x;
    return ss.str();
}

string toString(vector<vector<int>> &board)
{
    string ret = "";
    for (int i = 0; i < 2; i++)
    {
        for (int j = 0; j < 3; j++)
        {
            ret.append(NumberToString(board[i][j]));
        }
    }
    return ret;
}

int findStart(string &str)
{
    int i = 0;
    for (; i < 6; i++)
    {
        if (str[i] == '0')
        {
            return i;
        }
    }
}

void getAll(string &src, queue<string>&ret, set<string>&visSet)
{
    int start = findStart(src);
    string str = src;
    vector<int> vec = canGoVec[start];
    for (int i = 0; i < vec.size(); i++)
    {
        char c = str[start];
        str[start] = str[vec[i]];
        str[vec[i]] = c;
        if (visSet.count(str))
        {
            str = src;
            continue;
        }
        ret.push(str);
        visSet.insert(str);
        str = src;
    }
}

int slidingPuzzle(vector<vector<int>> &board)
{
    int count = 0;
    string target = "123450";
    set<string>visSet;
    queue<string>goVec;
    string start = toString(board);
    getAll(start,goVec, visSet);
    while (goVec.size()>0)
    {
        int size = goVec.size();
        count++;
        for (int i = 0; i < size; i++)
        {
            string tmp = goVec.front();
            if (tmp == target)
            {
                return count;
            }
            getAll(tmp, goVec, visSet);
            goVec.pop();
        }
    }
    return -1;
}