It is said that everything is difficult at the beginning, so I want to find a simple topic to write my first solution. My growth starts from now on and will not stop.

Title: you are trapped in a 3D dungeon and need to find the fastest way out! Dungeons consist of unit cubes that may or may not be filled with rock. It takes one minute to move a unit north, South, East, West, up or down. You can't move diagonally. The maze is surrounded by solid rocks on all sides. Can you escape? If so, how long will it take?

How to solve the problem: a very simple bfs problem only needs two more directions.

Width first search algorithm (also known as breadth first search) is one of the simplest graph search algorithms. This algorithm is also the prototype of many important graph algorithms. Dijkstra Single source shortest path Algorithm and Prim minimum spanning tree The algorithm adopts the idea similar to width first search. Its alias is BFS, which belongs to a blind search method. Its purpose is to systematically expand and check all nodes in the graph to find the results. In other words, it does not consider the possible location of the result and searches the whole graph thoroughly until it finds the result.

In my opinion, bfs can be used when you clearly know how to go. For example, for the current topic, we clearly know that there are six directions and the map, so I can use bfs.

Then what does bfs need? (what do we need to know from the beginning to the end)

1: Know the current position and the next position.

2: There is no place to go.

For the first problem, in bfs, we use a queue to store your location at that time, and then use the direction array. When you add the coordinates of the current position to the coordinates of the direction array, you can get the next position you want to go.

The position that can't be walked, the first is the position that can't be walked given in the title, and the second is the position that we have walked through. Obviously, the first problem is easy to know. The second problem needs to be completed with the help of an array. We can use a visit array to determine whether this position has been passed by us.

When we solve all the problems, it will be easy for us to solve them.

Tools: graph, visit array, structure queue, direction array, structure (a good way to record the current position).

Process: first, we input the diagram, then find out our starting point, record it with a structure, and then start bfs.

bfs:

Step 1: record the starting point into the queue, and then use the visit array to record this point as non queryable.

Step 2: we need many points in the queue, so we must use the loop. Then we need to find the exit of the loop. It's easy to know that the loop can end when the queue is empty or we find the end point. Let's set up a cycle, and then start each cycle from the head element of the queue (remember to take the head element out of the queue at this time), then find the coordinates you want to go next, and judge whether you can go, If you can walk, change the information of this point (change some variables according to the requirements of the topic, for example, each step in the topic will take 1s, so we need to add 1 to the coordinates and current time of each step, and then add them to the queue) and remember that we also need to exit this cycle when we reach the end. In this way, the bfs process is solved

Because I have also finished writing that topic, and there are more than a dozen search topics, I found that the first thing we need to learn is the way of thinking, and then the template. For example, how to write bfs is the template.

When solving problems, we must grasp the characteristics and commonalities of the problem. The characteristics are the differences between this problem and the problems you have written in your mind. We will solve these characteristics, and then what are the same with those problems? Remember, we don't need to spend more time thinking about the same points next time.

Last time code

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<queue>
int idx[]={0,0,0,0,1,-1};//
int idy[]={0,0,1,-1,0,0};//
int idz[]={-1,1,0,0,0,0};// The three together are the direction array
char maze[35][35][35];//chart
char v[35][35][35];//Tag array
using namespace std;
int l,r,c;//Layer l, row r, column c
typedef struct node
{
    int x,y,z;
    int t;
}Node;
Node S,E;
bool bfs()
{
    queue<Node>q;
    v[S.x][S.y][S.z]=true;
    q.push(S);
    while(!q.empty())
    {
        Node t=q.front();
        q.pop();
        for(int i=0;i<6;i++)
        {
            int x=t.x+idx[i];
            int y=t.y+idy[i];
            int z=t.z+idz[i];
            int d=t.t;
            if(x>=0&&x<l&&y>=0&&y<r&&z>=0&&z<c&&!v[x][y][z])//Judge whether this point can be passed
            {
                if(maze[x][y][z]=='.')
                {
                    q.push({x,y,z,d+1});
                    v[x][y][z]=true;
                }
            }
            if(maze[x][y][z]=='E')
                {
                    E.t=d+1;
                    return true;//If we search all the points we can reach, we will return yes at the end
                }
        }
    }
    return false;//If all the points we can go are searched or not, then return No
}
int main()
{
    while(cin >>l>>r>>c&&(l+r+c))
    {
        memset(v,false,sizeof(v));//Remember to update every time
        for(int i=0;i<l;i++)
        for(int j=0;j<r;j++)
        for(int k=0;k<c;k++)
        {
           cin>>maze[i][j][k];
           if(maze[i][j][k]=='S')
           {
               S.x=i;
               S.y=j;
               S.z=k;
               S.t=0;
           }
        }
        if(bfs())
            printf("Escaped in %d minute(s).\n",E.t);
        else
            cout <<"Trapped!"<<endl;
    }
    return 0;
}