C Data Structure Maze problem solving

Now on the Internet for a variety of maze solution, version of the countless. I small white 1, paste their own solution to the maze of this small project, I wrote. I hope I can help someone who is also in trouble. After all, I was puzzled for a while.

First of all, For the maze solution project, I first put forward my own ideas, using the method of "exhaustive solution" (Teacher Yan Weimin mentioned in the book of data Structure 1, 1 did not know the name of the method at the beginning.) In fact, it is simply a way to try one way, of course, can not casually try, my method is to start from the entrance, along the direction of the exploration, go on going; Otherwise, leave a mark and go back in the same direction until all the paths are covered. Or use the stack after the first out of the structure to save 1 route. The code USES the stack sequence to implement the structure of the array format (not elaborated on the stack).

// Call header file 
#ifndef AFXSTD_H
#define AFXSTD_H 
 
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<iostream>
using namespace std; 
// cout; cin;C++ I/O 
#endif

// Maze structure creation 
#ifndef MAZE_H
#define MAZE_H
 
#define ROWSIZE 10  // Size of the maze 
#define COLSIZE 10
#define Reachable 0 // I can go to 
#define Bar   1 // obstacles 
#define Foot  2 // footprint 
#define Mark  3 // Nonpassable marker 
typedef int MapType[ROWSIZE][COLSIZE]; //  The map type  
 
typedef struct 
{
 int row;// x
 int col;// y;
}PosType;     // Coordinate structure 
 
typedef struct
{
 int ord;   // The serial number of a passage block on a road 
 PosType seat;  // SIMS coordinates 
 int di; //  The direction of  // 1 2 3 4
}MElemType;  // Try the structure of the maze man 
 
typedef MElemType SElemType; //  and stack  associated 
 
 
 
bool MazePass(MapType maze,PosType curpos);
void FootPrint(MapType maze,PosType curpos);  // Footprint of print 
PosType NextPos(PosType curpos,int di);    // Under the 1 A position 
void MarkPrint(MapType maze,PosType curpos);   // Print non - passable mark 
bool MazePath(MapType maze,PosType start,PosType end); // The maze solves the core puzzle 
void PrintMap(MapType maze);       // Print the map 
 
 
#endif

// Stack structure 
#include"Maze.h"
#ifndef SEQSTACK_H
#define SEQSTACK_H
#define STACKSIZE 100
 
//typedef int SElemType;
 
struct SeqStack
{
 SElemType *data;
 int maxsize;
 int top;
};
 
void Init_Stack(SeqStack &st);
void Destroy_Stack(SeqStack &st);
void Stack_Clear(SeqStack &st);
bool Stack_Empty(SeqStack &st);
bool Stack_Full(SeqStack &st);
int Stack_Size(SeqStack &st);
bool Stack_Push(SeqStack &st,const SElemType &x);
bool Stack_Pop(SeqStack &st, SElemType &x);
 
SElemType GetTop(SeqStack &st);
void Pop(SeqStack &st);
 
#endif

So that's the creation of the header file, and the creation of the structure, and now you really feel the importance of the structure. Structure is not good to create their own to dig holes, remember to remember!!

Now post the code for the function and I'll try to explain it as clearly as I can. (I will elaborate on the stack problem again later, this time the focus is on the maze solution, so directly post the stack detailed code, please understand.)

// Here is the implementation of the stack 
#include"AfxStd.h"
#include"Stack.h"
 
bool Stack_Resize(SeqStack &st)
{
 SElemType *s = (SElemType*)malloc(sizeof(SElemType)*st.maxsize * 2);
 if(NULL == s) return false;
 for(int i = 0;i<= st.top;++i)
 {
 s[i] = st.data[i];
 }
 free(st.data);
 st.data = s;
 st.maxsize = st.maxsize * 2;
 return true;
}
void Init_Stack(SeqStack &st)
{
 st.maxsize = STACKSIZE;
 st.top = -1;
 st.data = (SElemType*)malloc(sizeof(SElemType)*st.maxsize);
 if(NULL == st.data)
 {
 exit(0);
 }
}
void Destroy_Stack(SeqStack &st)
{
 free(st.data);
 st.data = NULL;
 st.maxsize = 0;
 st.top = -1;
}
 
void Stack_Clear(SeqStack &st)
{
 st.top = -1;
}
bool Stack_Empty(SeqStack &st)
{
 return Stack_Size(st) == 0;
}
bool Stack_Full(SeqStack &st)
{
 return Stack_Size(st) == st.maxsize;
}
 
int Stack_Size(SeqStack &st)
{
 return st.top + 1;
}
 
bool Stack_Push(SeqStack &st,const SElemType &x)
{
 if(Stack_Full(st) && ! Stack_Resize(st))
 {
 return false;
 }
 st.data[++st.top] = x;
 return true;
}
bool Stack_Pop(SeqStack &st, SElemType &x)
{
 if(Stack_Empty(st))
 {
 return false;
 }
 x = st.data[st.top--];
 return true;
}

// Invoke the header file you created earlier 
#include"AfxStd.h"
#include"Maze.h"
#include"Stack.h"
 
 
/////////////////////////////////////////////////
 
bool MazePass(MapType maze,PosType curpos) // Decide whether or not it passes 
{
 return maze[curpos.row][curpos.col] == Reachable; // Determine whether the current node can pass 
}
void FootPrint(MapType maze,PosType curpos)  // Print the footprint  
{
 maze[curpos.row][curpos.col] = Foot;  
}
PosType NextPos(PosType curpos,int di)    // For the 1 The judgment of the direction of nodes 
{
 switch(di)
 {
 case 1: curpos.row+=1; break;// 1
 case 2: curpos.col-=1; break;// 2
 case 3: curpos.row-=1; break;// 3
 case 4: curpos.col+=1; break;// 4
 }
 return curpos;
}
void MarkPrint(MapType maze,PosType curpos)   // Nodes that cannot pass leave marks that cannot pass 
{
 maze[curpos.row][curpos.col] = Mark;
}
 
bool MazePath(MapType maze,PosType start,PosType end)// (core) Maze puzzle solving 
{
 bool res = false;       // define 1 a res Parameter is Boolean 
 PosType curpos = start;     // The current initial position is the entrance 
 int curstep = 1;        //  The initial exploration direction is 1
 SeqStack st;          // Path storage stack 
 MElemType e;          // Initial exploration villain 
 Init_Stack(st);         // Initialize the stack 
 do{
 if(MazePass(maze,curpos))     // The current position is passable, that is, the coordinates that have not been reached 
 {
 FootPrint(maze,curpos);    // footprint 
 e.di = 1, e.seat = curpos,e.ord = curstep++;
 Stack_Push(st,e);      // Join in the path 
 if(curpos.row == end.row && curpos.col == end.col)
 {
 res = true;
 break;
 }        // Reach the finish line 
 curpos = NextPos(curpos,1);  // To explore the 1 location 
 }
 else
 {
 if(!Stack_Empty(st))    // The current position cannot pass 
 {
 Stack_Pop(st,e);
 while(e.di == 4 && !Stack_Empty(st))
 {
  MarkPrint(maze,e.seat);  
  Stack_Pop(st,e);    //  Leave an impassable mark and return it 1 step 
 }
 if(e.di < 4)
 {
  e.di+=1;     //  substituted 1 Directional exploration 
  Stack_Push(st,e);   // Record path again 
  curpos = NextPos(e.seat,e.di); //  Adjacent blocks whose current position is set to the new direction 
 }
 }
 }
 }while(!Stack_Empty(st));  // Returns the failure parameter when the stack is empty and destroys the stack 
 Destroy_Stack(st);    
 return res;
}
void PrintMap(MapType maze)   // Print the map 
{
 for(int i = 0;i<ROWSIZE;++i)
 {
 for(int j = 0;j<COLSIZE;++j)
 {
 printf("%2d",maze[i][j]);
 }
 printf("\n");
 }
 printf("\n");
}

Above is a detailed explanation of the maze, I hope to help you. Add my test file later.

#include"AfxStd.h"
#include"Maze.h"
 
int main()
{
 MapType maze ={      //1 Start the map creation 
 {1,1,1,1,1,1,1,1,1,1},
 {1,0,1,1,1,1,1,1,1,1},
 {1,0,0,0,0,0,0,0,0,1},
 {1,0,0,0,1,1,1,1,0,1},
 {1,0,0,0,1,1,1,1,0,1},
 {1,0,1,1,1,1,0,0,0,1},
 {1,0,1,1,1,1,1,1,1,1},
 {1,0,0,0,0,0,0,1,1,1},
 {1,0,1,1,1,1,0,0,0,1},
 {1,1,1,1,1,1,1,1,1,1},
 };
 PosType start={1,1},end={8,8};
 PrintMap(maze);      // Print the initial map 
 MazePath(maze,start,end);
 PrintMap(maze);      // Print maze solution 
 return 0;
}