# C Data Structure Maze problem solving

• 2020-06-15 09:51:08
• OfStack

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).

``````
#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;
}
``````

Related articles: