Maze problem (BFS record path)

BFS Walking in a maze is generally two problems , The first is to ask the shortest route , The second is to ask the shortest path length , Today, I'd like to introduce you to the first output maze path .

Let's start with a classic example ：

Define a two-dimensional array ：
int maze[5][5] = {
0, 1, 0, 0, 0,
0, 1, 0, 1, 0,
0, 0, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 1, 0,
};
It means a maze , Among them 1 Wall ,0 Means the way to go , You can only walk horizontally or vertically , Don't walk sideways , Ask the program to find the shortest route from the top left corner to the bottom right corner .

Output the shortest route from the upper left corner to the lower right corner of the maze
SampleOutput
(0, 0)
(1, 0)
(2, 0)
(2, 1)
(2, 2)
(2, 3)
(2, 4)
(3, 4)
(4, 4)

What is your first thought when you see the problem ？ I was just trying to use BFS How to record the path if you write it , because BFS It's written like a queue （ Join the team , One side out of the team ）, Thought for a long time , I also found a lot of articles on the Internet to read , But I can't find the answer I want , Looking at many articles, I suddenly got inspiration , Thought of how to record the path .

AC The code and comments are as follows ：

#include<iostream>
#include<algorithm>
using namespace std;

const int N = 100;
const int M = 100005;

struct node {
    
	int x, y;
}w[M];

int mp[N][N];// Save the map 
int ans[M];// Used to record the number of steps taken 

// Use vectors to search up, down, left and right 
int dx[4] = {
     0,1,-1,0 };
int dy[4] = {
     1,0,0,-1 };

void dfs(int u)
{
    
  // Only uninitialized ans[0]=0 Satisfy ans[u]==u, Everything else has ans[u]>u;
    if(ans[u]==u)
    {
    
        printf("(0, 0)\n");
        return ;
    }
    dfs(ans[u]);
    printf("(%d, %d)\n",w[u].x,w[u].y);
}

void bfs(int x, int y)
{
    
	int head = 0, tail = 0;
	int flag=0;//flag It is used to mark whether the destination has been reached 
	w[tail++] = {
     x,y };// Simulation queue 
	while (head != tail)
	{
    
		for (int i = 0; i < 4; i++)// Guang Shu , Expand in four directions 
		{
    
			int nx = w[head].x + dx[i];
			int ny = w[head].y + dy[i];
			// Judge whether the point meets the conditions 
			if (nx < 0 || nx >= 5 || ny < 0 || ny >= 5||mp[nx][ny]==1)continue;
			// If the conditions are met, join the team at this point 
			w[tail] = {
     nx,ny };
			// Here we use the initial time head and tail Unequal to save steps 
			// Let's go tail The coordinates of the previous point of the step are (w[head].x, w[head].y)
			ans[tail]=head;// Record where the previous point of the point is 
			tail++;
			if(nx==4&&ny==4)
            {
    
                flag=1;
                break;
            }
		}
		if(flag==1)
        {
    
            dfs(tail-1);// Start the output operation 
            break;
        }
        head++;
	}
}
int main()
{
    
    for(int i=0;i<5;i++)
        for(int j=0;j<5;j++)
        cin>>mp[i][j];
    bfs(0,0);// Start from the starting point and search widely 
}

The above is what I want to introduce today BFS The problem of finding the shortest route , If you have your own views on the content , Please give me your advice .