941 · Sliding Puzzles

In a block size is  2x3 的板上,有 5 block tile,分别用整数 1 到 5 表示,There is also an open space 0 表示.

One move representation 0 Swap places with a number in one of the four directions adjacent to it.

当且仅当 这块板 The tile placement status on  [[1,2,3],[4,5,0]] 时,It can be said that the problem of this board has been solved.

Given a puzzle,Returns the minimum number of moves required,to resolve the state of the board.If unable to resolve the state of the board,则返回-1.

• board will be mentioned above 2 x 3 The size is entered as an array .
• 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`.

解释: 
No matter how many steps you move, it won't solve the problem.

样例 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;
}