[programming problem] maze problem

Define a two-dimensional array NM, Such as 55 The array looks like this ：

int maze[5][5] = {
    
  0,1,0,0,0,
  0,1,1,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 sideways or vertically , Don't walk sideways , Ask the programmer to find the route from the upper left corner to the lower right corner , The entry point is [0,0], Since the first grid is the way to go .

Input description ：

Enter two integers , Respectively represent the number of rows and columns of a two-dimensional array . Then enter the corresponding array , among 1 Wall ,0 Means the way to go .

Output description ：

The shortest path from the top left corner to the bottom right corner , Format example .

Example ：

 Input ：
5 5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 1
0 1 1 1 0
0 0 0 0 0

 Output ：
(0,0)
(1,0)
(2,0)
(3,0)
(4,0)
(4,1)
(4,2)
(4,3)
(4,4)

We can use backtracking to find the shortest path . The specific steps are: ：

1. First, add the current point to the path , And set it to gone

2. Judge whether the current point is an exit , If yes, the output path , Save results ; Jump to 4

3. Judge the top of the current point in turn 、 Next 、 Left 、 Whether the four points on the right can go , If you can go, go to this point recursively

4. Current point push path , Set to walkable

Specific code

#include<iostream>
#include<vector>
using namespace std;
 
int N, M; // Represent rows and columns respectively 
vector<vector<int>> maze;// Maze matrix 
vector<vector<int>> path_temp;// Store the current path , The first dimension represents the position 
vector<vector<int>> path_best;// Store the best path 
 
void MazeTrack(int i, int j)
{
    
    maze[i][j] = 1;// Indicates that the current node has left , No more 
    path_temp.push_back({
     i, j });// Add the current node to the path 
    if (i == N - 1 && j == M - 1) // Judge whether the destination is reached 
        if (path_best.empty() || path_temp.size() < path_best.size())
            path_best = path_temp;
    if (i - 1 >= 0 && maze[i - 1][j] == 0)// Explore whether it's possible to go up 
        MazeTrack(i - 1, j);
    if (i + 1 < N && maze[i + 1][j] == 0)// Explore whether it's feasible to go down 
        MazeTrack(i + 1, j);
    if (j - 1 >= 0 && maze[i][j - 1] == 0)// Explore the feasibility of going left 
        MazeTrack(i, j - 1);
    if (j + 1 < M && maze[i][j + 1] == 0)// Explore the feasibility of going right 
        MazeTrack(i, j + 1);
    maze[i][j] = 0;         // Restore the scene , Set as not gone 
    path_temp.pop_back();
}
int main()
{
    
    while (cin >> N >> M)
    {
    
        maze = vector<vector<int>>(N, vector<int>(M, 0));
        path_temp.clear();
        path_best.clear();
        for (auto &i : maze)
            for (auto &j : i)
                cin >> j;
        MazeTrack(0, 0);// Trace back to find the shortest path in the maze 
        for (auto i : path_best)
            cout << '(' << i[0] << ',' << i[1] << ')' << endl;// Output path 
    }
    return 0;
}