迷宫求解C/C++

2019-11-06 07:35:42

字体：大中小

来源：转载

供稿：网友

迷宫求解

利用数据结构中的栈来求解迷宫路径，方法很简单，课本上也有很详细的问题解法，直接放代码：PS（代码可以直接运行，参数都放好了，要改可以在main()函数中修改，下次再放一个用BFS求迷宫的最优路径以及求解全部路径的算法。）#include <iostream>#include <malloc.h>using namespace std;#define STACK_INIT_SIZE 10#define STACK_INCREMENT 2#define MAX 10typedef struct{ int x; int y;}MazePos;typedef struct{ MazePos *top; MazePos *base; int StackSize;}SqStack;void InitStack(SqStack &S){ S.base = (MazePos *) malloc (STACK_INIT_SIZE * sizeof(MazePos)); S.top = S.base; S.StackSize = STACK_INIT_SIZE;}bool StackEmpty(SqStack S){ if(S.top == S.base) return true; else return false;}void Push(SqStack &S, MazePos e){ if((S.top - S.base) >= S.StackSize){ S.base = (MazePos *) realloc (S.base, (S.StackSize + STACK_INCREMENT) * sizeof(MazePos)); S.top = S.base + S.StackSize; S.StackSize += STACK_INCREMENT; } *S.top = e; ++S.top;}void Pop(SqStack &S, MazePos &e){ if(!StackEmpty(S)) e = *--S.top;}void GetTop(SqStack S, MazePos &e){ if(S.top > S.base) e = *--S.top;}void visit(MazePos e){ cout<<"("<<e.x<<","<<e.y<<")";}void StackTraverse(SqStack S){ int i = 0; cout<<"start"; while(S.base < S.top){ cout<<"->"; visit(*S.base++); if(++i%8 == 0) cout<<endl; } cout<<"->end"<<endl;}void MazePRint(int Maze[][MAX], int n,int m){ for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++) printf("%3d",Maze[i][j]); cout<<endl; }}void MazePath(int Maze[][MAX], MazePos start, MazePos end){ int flag,count = 1; MazePos curpos; SqStack s; InitStack(s); curpos = start; if(!Maze[start.x][start.y] || !Maze[end.x][end.y]) goto loop; do{ if(Maze[curpos.x + 1][curpos.y] == 1){ Push(s,curpos); ++curpos.x; flag = 1; } else if(Maze[curpos.x][curpos.y + 1] == 1){ Push(s,curpos); ++curpos.y; flag = 1; } else if(Maze[curpos.x - 1][curpos.y] == 1){ Push(s,curpos); --curpos.x; flag = 1; } else if(Maze[curpos.x][curpos.y - 1] == 1){ Push(s,curpos); --curpos.y; flag = 1; } else flag = 0; if(flag) Maze[curpos.x][curpos.y] = ++count; else{ Maze[curpos.x][curpos.y] = 0; Pop(s,curpos); --count; } }while((curpos.x != end.x || curpos.y != end.y) && !StackEmpty(s)); if(curpos.x == end.x && curpos.y == end.y){ cout<<"Yes!"<<endl; MazePrint(Maze, MAX, MAX); StackTraverse(s); } else loop:cout<<"No!"<<endl;}int main(){ int Maze[MAX][MAX]={ {0,0,0,0,0,0,0,0,0,0}, {0,1,0,1,0,1,1,1,1,0}, {0,1,1,1,0,1,0,1,0,0}, {0,0,1,0,0,0,1,1,1,0}, {0,1,1,1,1,1,1,0,1,0}, {0,0,0,0,0,0,0,0,1,0}, {0,1,1,1,1,1,1,1,1,0}, {0,1,0,0,0,0,0,0,0,0}, {0,1,1,1,1,1,1,1,1,0}, {0,0,0,0,0,0,0,0,0,0}}; MazePos start, end; start.x = start.y = 1; end.x = end.y=8; cout<<"Print Maze"<<endl; MazePrint(Maze, MAX, MAX); MazePath(Maze, start, end); return 0;}

上一篇：c++复习之重载运算符

下一篇：把qt中的qdebug()宏定义成C++类型的cout