UVA816 Abbott’s Revenge

Title

 

 

Ideas

        By using BFS Traverse the maze to find the shortest path .for Loop simulation goes in three directions . If you can walk in one direction , Record where you went , Join the queue , So that we can find our way to it later . Record its previous node , And calculate the distance , The distance to the node is the distance from the previous node plus one .

for (int i = 0; i < 3; i++) // Straight left and right 
{
    node gone = walk(now, i); // Suppose you take one step 
    // The first condition determines whether the steering is allowed , The second condition determines whether the coordinates are in the maze , The third coordinate determines whether the point has passed 
    if (maze[now.row][now.col][now.dir][i] && legal(gone.row, gone.col) && dis[gone.row][gone.col][gone.dir] == -1)
    {
        q.push(gone); // Join the queue for the next step BFS
        // Record the distance , Pre record node 
        dis[gone.row][gone.col][gone.dir] = dis[now.row][now.col][now.dir] + 1;
        nbefore[gone.row][gone.col][gone.dir] = now;
}

 walk Function turn value 0 1 2 Respectively ： Go straight on 、 Turn left 、 Right turn . Go straight in the same direction , So there is no need to be right dir Deal with .

For direction string const char *dirs = "NESW";dir Is its numerical representation . Turn left （ Suppose it is E, Turn left and then N） Then this function can dir Deal with it as dirs The previous digit of the value represents . The same goes for the right .

node walk(const node &n, int turn)
{
    int dir = n.dir;
    switch (turn)
    {
    case 1:
        dir = (dir + 3) % 4; // Turn left to update the direction dirs Previous , Anticlockwise 
        break;
    case 2:
        dir = (dir + 1) % 4; // Turn right to update the direction dirs The latter one , clockwise 
    }
    return node(n.row + rc[dir][0], n.col + rc[dir][1], dir);
}

1. utilize int dir_id(char ch), int turn_id(char ch) The function converts the direction and direction of the maze into a numerical representation .
2. bool maze[10][10][4][3] It is used to represent the maze abstractly , The first two dimensions are row and column coordinates , The third dimension represents the orientation of the current position , The fourth dimension represents steering . That is, if an array value is true , Indicates that you can turn to a certain direction in the current row and column coordinates .
3. int dis[10][10][4] Indicates the distance between the current coordinate and the current orientation relative to the starting point .
4. node nbefore[10][10][4] It is used to record the current coordinates and the previous node on the path of the current orientation . So that when outputting , Follow nbefore Data backward path of .
5. node walk(const node &n, int turn) It can represent a step forward in the maze

Refer to liurujia 《 Classic introduction to algorithm competition （ The second edition ）》

 

#include <iostream>
#include <queue>
#include <string>
#include <cstring>
using namespace std;
struct node
{
    int row, col, dir;
    node(int r = -1, int c = -1, int d = -1) : row(r), col(c), dir(d) {}
};
bool maze[10][10][4][3];                                 // Describe the maze 
int dis[10][10][4];                                      // Distance to entrance 
node nbefore[10][10][4];                                 // Save the previous node 
const char *dirs = "NESW";                               // North, Southeast and West 
const char *turns = "FLR";                               // Straight left and right 
const int rc[4][4] = {
   {-1, 0}, {0, 1}, {1, 0}, {0, -1}}; // The change of North, Southeast and West coordinates 
//strchr It's about finding ch stay dirs Subscript in , Use subscripts to indicate orientation and steering 
int dir_id(char ch) { return strchr(dirs, ch) - dirs; }
int turn_id(char ch) { return strchr(turns, ch) - turns; }
node walk(const node &n, int turn); // Take a step in the maze 
// Determine whether the coordinates are legal 
bool legal(int row, int col) { return row >= 1 && row <= 9 && col >= 1 && col <= 9; }

int main()
{
    string name;
    while (cin >> name && name != "END")
    {
        cout << name << endl;
        int row, col;
        char ch;
        cin >> row >> col >> ch;
        node start(row, col, dir_id(ch)); // Starting point 
        cin >> row >> col;
        node end(row, col, 0); // The end , Face casually 
        memset(maze, 0, sizeof(maze));
        while (cin >> row && row != 0) // Maze data input 
        {
            cin >> col;
            string str;
            while (cin >> str && str != "*")
                for (int i = 1; i < str.size(); i++)
                    maze[row][col][dir_id(str[0])][turn_id(str[i])] = true;
            // The four dimensions represent the position, direction and direction respectively , For true Is able to turn , On the contrary, we can't 
        }

        memset(dis, -1, sizeof(dis));
        node now = walk(start, 0);          // Take a step from the starting point to the maze , Because the direction of the starting point is determined , This step also determines ,0 It means no turning 
        dis[now.row][now.col][now.dir] = 1; // Note that the distance between this position and the starting point is 1
        queue<node> q;
        q.push(now);
        bool isout = false;
        while (!q.empty()) //BFS
        {
            now = q.front();
            q.pop();
            if (now.row == end.row && now.col == end.col) // When you reach the destination, you will output the result 
            {
                isout = true;
                vector<node> vec;
                while (dis[now.row][now.col][now.dir] != 1) // Path push back , Save to array 
                {                                           // Because nbefore The previous node information of the current node is saved 
                    vec.push_back(now);
                    now = nbefore[now.row][now.col][now.dir];
                }
                vec.push_back(walk(start, 0));
                vec.push_back(start);
                // Format output 
                int count = 0;
                for (int i = vec.size() - 1; i >= 0; i--)
                {
                    if (++count % 10 == 1)
                        cout << ' ';
                    cout << " (" << vec[i].row << ',' << vec[i].col << ")";
                    if (count % 10 == 0)
                        cout << endl;
                }
                if (vec.size() % 10 != 0)
                    cout << endl;
                break; // The current maze has been solved , sign out BFS Cycle 
            }
            else // Otherwise, it will follow BFS
            {
                for (int i = 0; i < 3; i++) // Straight left and right 
                {
                    node gone = walk(now, i); // Suppose you take one step 
                    // The first condition determines whether the steering is allowed , The second condition determines whether the coordinates are in the maze , The third coordinate determines whether the point has passed 
                    if (maze[now.row][now.col][now.dir][i] && legal(gone.row, gone.col) && dis[gone.row][gone.col][gone.dir] == -1)
                    {
                        q.push(gone); // Join the queue for the next step BFS
                        // Record the distance , Pre record node 
                        dis[gone.row][gone.col][gone.dir] = dis[now.row][now.col][now.dir] + 1;
                        nbefore[gone.row][gone.col][gone.dir] = now;
                    }
                }
            }
        }
        if (isout == false) // If no path result is output 
            cout << "  No Solution Possible" << endl;
    }
    return 0;
}

node walk(const node &n, int turn)
{
    int dir = n.dir;
    switch (turn)
    {
    case 1:
        dir = (dir + 3) % 4; // Turn left to update the direction dirs Previous , Anticlockwise 
        break;
    case 2:
        dir = (dir + 1) % 4; // Turn right to update the direction dirs The latter one , clockwise 
    }
    return node(n.row + rc[dir][0], n.col + rc[dir][1], dir);
}