This is the 17th day of my participation in the More text Challenge. For more details, see more text Challenge

Preface: someone has given such an example, give you zhang Peking University’s admission notice first, but ask you to get up at 5 o ‘clock every day, go to bed at 12 o ‘clock 😪, study assidiously, diligent make progress. The notice is valid as long as you stick to it for three years. If it were you, would you be able to hold on? In fact, this example is very difficult to show in our life, because it has a clear goal, there is an exact route. As long as you follow this way, there will be no problem. But most of the time we don’t have such a route, and we don’t even know how long it takes to reach our own dawn. But!!! Who doesn’t long for the dawn? Hang in there!

773. Slide puzzle

On a 2 x 3 board, there are five tiles, represented by the numbers 1 to 5, and a vacancy represented by a 0. A move is defined as selecting 0 to swap with an adjacent number (top, bottom, left, right). Finally when the result of the board board 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 that can be made to solve the puzzle board, or -1 if the puzzle board cannot be solved.

Example:

Input: board = [[1,2,3],[4,0,5] output: 1 explanation: switch 0 and 5, 1 step complete input: board = [[1,2,3],[5,4,0] output: -1 explanation: there is no way to complete the puzzle board input: Board = [[3,2,4],[1,5,0]] output: 14 input: board = [[4,1,2],[5,0,3] output: 5 explanation: the minimum number of moves to complete the puzzle board is 5. A move path: not yet moved: ,1,2 [[4], [5,0,3]] move 1: [,1,2 [4], [0,5,3]] move 2 times: [[0], [4,5,3]] move three times: [,0,2 [1], [4,5,3]] move four times: [[1,2,0],[4,5,3]] moves 5 times: [[1,2,3],[4,5,0]]Copy the code

Methods a

For the most short-circuited problem with a weight of 1, the first thought is to use breadth first search, starting from the initial state and adding to the queue those legitimate states that can be transferred from the queue head each time. When each element is queued, determine whether it is the desired answer, and if it is, return. Otherwise, keep searching. If the answer is not found until the queue is empty, the initial state cannot be transferred to the answer and -1 is returned.

Details: a two-dimensional checkerboard like this state is represented by a one-dimensional string; They say you can only move 0 up, down, around, up, minus 3, down, left, minus 1, right, plus 1; Use a hash table to record which states have been accessed to prevent re-enqueueing and creating an infinite loop. A hash table stores a pair of keys and values, where key is the state, and value is the minimum number of steps to take from the initial state to the key state.

    class Solution {
    public:
        typedef pair<string, int> PSI;
        int slidingPuzzle(vector<vector<int>>& board) {
            unordered_map<string, bool> st; / / a hash table
            int dx[4] = {- 3.3.1.- 1}; // Four methods
            string start; // Initial state
            for (int i = 0; i < 2; i ++ )
                for (int j = 0; j < 3; j ++ )
                    start += board[i][j] + '0';
    
            queue<PSI> q; 
            q.push({start, 0});
            st[start] = true;
            while (q.size()) {
                auto t = q.front(a); q.pop(a);if (t.first == "123450") return t.second; // If it is the answer, return
    
                int index = t.first.find('0');
                for (int i = 0; i < 4; i ++ ) { // Enumerate the four methods
                    int idx = index + dx[i];
                    if (idx == 2 && index == 3 || idx == 3 && index == 2) continue; // Determine whether it is legitimate
                    if (idx >= 0 && idx < 6) {
                        string temp = t.first;
                        swap(temp[index], temp[index + dx[i]]);
                        if(! st[temp]) {// It is legal and has not been in a team before
                            st[temp] = true;
                            q.push({temp, t.second + 1}); }}}}return - 1; }};Copy the code

Note: when calculating the state transfer are legal, in accordance with the above code to add the if (independence idx = = 2 && index = = | 3 | independence idx = = 3 && index = = 2) continue; This row, this is the exclusion of the fact that the last column in the first row swaps with the first column in the second row, which is illegal.

The complexity of the

Time complexity: O((nm)! 4nm), n*m checkerboard has O((nm)!) In each case, you need to find where 0 is and iterate through its four methods O(4nm).

Space complexity: O((nm)! At most, you need to store (nm) in the queue! A string of length nm.