This is the 26th day of my participation in the genwen Challenge

Topic describes

On a 2 x 3 board, there are five tiles, represented by numbers 1 to 5, and a vacancy represented by a 0.

A move is defined as choosing 0 to swap with an adjacent number (up, down, left, and right).

Finally when the board result is [[1,2,3],[4,5,0]] the puzzle board is solved.

Given the initial state of a puzzle board, return the minimum number of moves it can take to solve the puzzle board, or -1 if it cannot be solved.

Example:

Input: board = [[1,2,3],[4,0,5]] output: 1 explanation: swap 0 and 5, step 1 completeCopy the code
Input: board = [[1,2,3],[5,4,0]] output: -1 explanation: there is no way to complete the boardCopy the code
Input: board = [[4,1,2],[5,0,3]] output: 5 explanation: the minimum number of moves to complete the puzzle board is 5, one movement path: not moved: [[4,1,2],[5,0,3]] moved 1 time: ,5,3,1,2 [[4], [0]] move 2 times: [[0], [4,5,3]] move three times: [,0,2 [1], [4,5,3]] move four times: [[1 0], [4,5,3]] move 5 times: [[1, 2, 3], [4,5,0]]Copy the code
Input: board = [[3,2,4],[1,5,0]Copy the code

Tip:

  • boardIs an array of 3 x 3 as described above.
  • board[i][j]Is a permutation of 0, 1, 2, 3, 4, 5.

Their thinking

We can use breadth-first search to find the minimum number of swaps from the initial state board to the target state [[1,2,3],[4,5,0]].

Specifically, we queue (board,0) at the beginning and use that queue for breadth-first search. In the process of searching, set the current searched status as status and the number of operations as step. We can enumerate the status obtained through one operation. Let one of these states be next_status, and if it has not been searched, we queue (next_status,step+1). If we find target, we return the number of operations.

In the process of searching, we need a hash table to store all the searched states to avoid repeated searches.

If [[1,2,3],[4,5,0]] is still not found after the search is completed, it means that we cannot solve the puzzle board and return to −1

code

C + + code

class Solution {
private:
    vector<vector<int>> neighbors = {{1.3}, {0.2.4}, {1.5}, {0.4}, {1.3.5}, {2.4}};

public:
    int slidingPuzzle(vector<vector<int>>& board) {
        // enumeration status The status obtained by an exchange operation
        auto get = [&](string& status) -> vector<string> {
            vector<string> ret;
            int x = status.find('0');
            for (int y: neighbors[x]) {
                swap(status[x], status[y]);
                ret.push_back(status);
                swap(status[x], status[y]);
            }
            return ret;
        };

        string initial;
        for (int i = 0; i < 2; ++i) {
            for (int j = 0; j < 3; ++j) {
                initial += char(board[i][j] + '0'); }}if (initial == "123450") {
            return 0;
        }

        queue<pair<string, int>> q;
        q.emplace(initial, 0);
        unordered_set<string> seen = {initial};

        while(! q.empty()) {
            auto [status, step] = q.front(a); q.pop(a);for (auto&& next_status: get(status)) {
                if(! seen.count(next_status)) {
                    if (next_status == "123450") {
                        return step + 1;
                    }
                    q.emplace(next_status, step + 1);
                    seen.insert(move(next_status)); }}}return - 1; }};Copy the code