Exercise --- BFS

Eight digital

 

If you want to find the shortest path or the minimum number of operation steps , Deep search is impossible , We need to use wide search , This is it. DFS and BFS The difference between

DFS The node found for the first time is not necessarily found along the shortest path ,BFS The node found for the first time must be searched along the shortest path

Given a 3 × 3 The grid of , There are 1 To 8 These eight numbers and one ' x ', This ' x ' It's actually a space , There are no numbers in it , Every time you can move an existing number into a space , For example, the following picture , The position of the space is shown in the figure , What we can do is to move the numbers in the four boxes around the space to the space , Moving once is an operation , The first is to put 1 Move to x Go inside this space , The second case is to put 4 Move to x Go inside this space , The third case is to put 7 Move to x Go inside this space , There are three ways to move in this state

The title gives us an initial state , Let's do the same operation several times , Change the initial state into the given result state , Ask how many transformations are needed at least to meet such a requirement , If the result state cannot be reached, output -1

For example, the initial state given by the title can be transformed three times to get the final result state , The first step is to put 4 and x Exchange to get the first state , Step 2 5 and x Exchange to get the second state , Step 3 8 and x Exchange to get the final state

The question requires the minimum number of steps , So you can use BFS To do it , We can abstract , Look at all States as a point in the diagram , If one state can change into another state after one transformation ( Put state a Change into a state b) Words , Just connect one from a Point to b The edge of , The weight of the edge is 1, The problem will be transformed into giving us a starting point , ask ： How many steps does it take to walk from the beginning to the end ？ The weight of all edges is 1, So you can use BFS To find the shortest path , If you can't walk from the beginning to the end, return -1

The difficulty of this problem is that the state representation is relatively complex , Generally speaking, a state or a node can be represented by a number , For example, nodes 1、 node 2、 node 3 . . . Every state here is a 3 × 3 The small matrix of , It's not very convenient to express , When searching for the shortest path with width , Two data structures need to be defined , The first is the queue , How to store the status in the queue , This is the first question ; How to record the distance of each state 【dist Implementation distance of array , How to represent the subscript of the distance array ？】, This is the second question , The difficulty is to deal with the above problems

There are many ways to store this question , A relatively simple way is to directly use strings to represent all States , The whole 3 × 3 The array of is expanded into a line , Then use a string to express , When defined in the queue , Directly defined as queue＜string＞ That's all right. ,dist It can be used c++ The hash table inside , perhaps python Dictionary in , perhaps java The dictionary inside stores

The second problem is how to do state transition , How to see what other states this state can go to , This is also more complicated , For example, give us a string "1234×5678", How to judge which states this state can become ？

It needs to be done in two steps , The first step is to restore it to 3 × 3 The appearance of , The second step is to transfer , In fact, transfer is to × The upper, lower, left and right positions of are enumerated respectively , Move its upper, lower, left and right numbers to × In the right place , Finally, put the moved 3 × 3 The matrix of is restored to a string

In the string, if x The subscript of is 4 Words , hold x convert to 3 × 3 Matrix , What is its horizontal and vertical coordinates ？ It can be used int x = k / 3,y = k % 3;

#include <iostream>
// Store all distances in a hash table 
#include <unordered_map>
// The queue needed for wide search 
#include <queue>
#include <algorithm>

using namespace std;

//BFS Find the shortest distance 
int bfs(string start)
{
    // Definition end End point 
    string end = "12345678x";
    // The queue needed for wide search 
    queue<string> q;
    // Define a distance array 
    unordered_map<string, int> d;
    // The first start Put it in the queue 
    q.push(start);
    // The distance from the starting point to the starting point is 0
    d[start] = 0;
    
    // Up, down, left and right 
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

    // Wide search process 
    while(q.size())
    {
        auto t = q.front();
        q.pop();
        // Use a variable to store t Distance of 
        int distance = d[t];

        // Determine if the t If it is the end, it can end ahead of time 
        if(t == end) return distance;
        
        // State shift   Take a look at what the current state can become   Before the state transition, you need to find x The location of   use k Storage x The location of  find('x') return x The subscript 
        int k = t.find('x');
        //[ Common skills ]  You can convert the subscript of a one-dimensional array into the subscript of a two-dimensional array  x、y It is the present. x The location of 
        int x = k / 3, y = k % 3;
        // Enumerate which number to put   hold x Move the four numbers up, down, left and right to x In the right place 
        for(int i = 0;i < 4;i++ )
        {
            //a、b Express x、y The coordinates of a number in the four directions up, down, left, right 
            int a = x + dx[i], b = y + dy[i];
            // If a and b Not out of bounds 
            if(a >= 0 && a < 3 && b >= 0 && b < 3)
            {
                //x、y Is the position of the space  a、b yes x、y A number in the middle of up, down, left and right   The goal now is to a、b This number moves to x、y Up   It's just exchange a、b and x、y
                swap(t[k], t[a * 3 + b]);
                // Status update  x、y The subscript of is k  two-dimensional a、b What is the subscript of the corresponding one-dimensional array ? a * 3 + b
                
                // After status update 
                if(!d.count(t))
                {
                    // If after the current update t If you haven't found it before   Found a new state   Need to update the distance of the new status 
                    d[t] = distance + 1;
                    // Add the new status to the queue 
                    q.push(t);
                }
                // Restore the state 
                swap(t[k], t[a * 3 + b]);
            }
        }
    }
    // If you can't find the end, you can't reach the end   return -1
    return -1;
}

int main()
{
    //start Store initial state   Read in first 9 Characters 
    for(int i = 0;i < 9;i++ )
    {
        char c;
        cin >> c;
        start += c;
    }
    //BFS
    cout << bfs(start) << endl;
    
    return 0;
}