[Data Structure] Stack Realizing the Law Problem of Maze

Thinking:

Solve the problem of solving the maze, start from the entrance and explore in a certain direction , If you can get through, then continue to move forward; otherwise, retreat along the original road, change the direction and continue to explore until all possible paths have been explored. In order to ensure that it can be returned along the original path at any position, a last-in first-out structure is needed to save the path from the entrance to the current position. Therefore, in the algorithm for finding the maze path, the idea of ​​”stack” should be applied, assuming that “current position” refers to “in the search process The basic idea of ​​the algorithm for finding a path in the maze is: if the current position is “passable”, put in the “current path” and continue to the “next position” “Explore”, that is, switch the “next position” to the “current position”, and repeat until you reach the exit; if the current position is “not accessible”, you should follow the “coming direction” and return to the “previous channel block”, and then move toward Continue to explore in other directions except the “coming direction”; if the four squares around the channel block are “unreachable”, the channel block should be deleted from the “current path”. The so-called “next position” refers to the adjacent squares in 4 directions (up, down, left, and right) around the current position. Assuming that the “current path” is recorded by the stack, the top of the stack is “the last channel block on the current path”. Thus, the operation of “putting into the path” is “pushing into the stack at the current position”; the operation of “deleting the previous channel block from the current path” is the “pulling”.

Code block

maze.h< /span>

#define _CRT_SECURE_NO_WARNINGS 1#include#include #include #include using namespace std; #define N 10struct pos {size_t _row; size_t _col;};stack  minstack;void GetMaze(int arr[][N],int size){ FILE* f = fopen("MAP.txt", "r" ); if (NULL == f){ cout << "Failed to open file" << endl; exit(-1);} for (int i = 0; i =0)&&(next._row<=N)&&(next._col>=0)&&(next._col<=N)&&arr[next. _row][next._col]==0) {return true;} else {return f alse; }}void PrintMaze(int arr[][N],int size){ for (int i=0;i& path){ //found Access path.push(entry); arr[entry._row][entry._col] = 2; while (!path.empty()) {pos cur = path.top(); pos next = cur; if (cur. _row == N-1 || cur._row == 0 || cur._col == N-1 ){ //Update the shortest path if (minstack.empty()) minstack = path; else if (path.size( ) 
 Test code block: 

#define _CRT_SECURE_NO_WARNINGS 1#include#include # include #include "maze.h"using namespace std;#define N 10int main(){ int mazeMap[N][N] = {0 }; GetMaze(mazeMap, N); PrintMaze(mazeMap, N ); stack path; pos entry = {2,0}; //Define the maze entry bool ret = MazePath(mazeMap,entry,path); if (ret){ PrintMaze(mazeMap, N); while (!minstack .empty()){ cout << "<" << minstack.top()._row << "," << minstack.top()._col << ">" << endl;; minstack.pop() ;}} system("pause"); return 0;}
 Map file
map.txt

1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 10 0 0 0 0 1 1 1 1 11 1 0 1 0 1 1 1 1 1 11 1 0 1 0 0 0 1 1 11 1 0 1 1 1 0 1 1 11 1 0 1 1 1 0 1 1 11 1 0 0 1 1 0 1 1 11 1 1 1 1 1 0 1 1 11 1 1 1 1 1 0 1 1 1
 Running result graph