| DFS遍历迷宫输出所有路径（借助数据结构栈） | 您所在的位置：网站首页 › 迷宫音箱结构图详解 › DFS遍历迷宫输出所有路径（借助数据结构栈） |
DFS遍历迷宫输出所有路径（借助数据结构栈）
|
写在前面
可解决问题：输入n,m，可随机生成n*m大小的迷宫(伪随机数),也可手动输入迷宫,找到迷宫中的所有可行路径（八个方向：上下左右以及对角），输出路径以及路径长度。 实现效果（更新）
......太多了
（觉得麻烦可以直接跳到最后） C语言实现栈，并打成头文件方便使用： #ifndef stack_h #define stack_h #include #include //栈中存位置以及遍历时所走的方向，打印时可以显示出来 typedef struct Node{ int x; int y; // int dir; //-1为左上右下对应 '\' 0为上下对应'|' 1为左右对应'——' 2为左下右上对应'/' struct node* next; }Node; typedef Node* Stack; //定义数据结构栈 Stack //-----------创建一个空栈-------------- Stack creakEmptyStack(){ Stack p; p=(Stack)malloc(sizeof(Node)); //申请一个空间 if(p){ p->next=NULL; return p; } else{ printf("No space!\n"); //申请空间失败则提示并返回空 return NULL; } } //------------将元素压入栈---------------- void push(int x,int y,Stack s){ Stack p; p=(Stack)malloc(sizeof(Node)); if(p){ //如果申请空间成功则用头插法将元素压入 p->x=x; p->y=y; if(!s->next) p->next=NULL; //如果此时栈里还没有任何元素，则p此时为第一个结点 else p->next=s->next; //否则将p插入头结点之后 s->next=p; } else{ printf("No space!\n"); } } //-------------检测栈是否为空-------------- int isEmpty(Stack s){ //为空则返回1，不为空返回0 if(s->next==NULL) return 1; else return 0; } //--------------将元素弹出栈---------------- void pop(Stack s){ Stack p; p=s->next; if(p->next){ s->next=p->next; free(p); } else return; } //------------取栈顶元素------------------ Node top(Stack s){ Node t; //判断是否为空，若不为空则返回 t=*(s->next); return t; } #endifC语言实现迷宫的遍历并输出所有的路径： 当然这里用c++的STL库的stack也可，但是下面的代码需要做一些小小的修改。 /* filename: 数据结构实验_迷宫.c * brife: Sovle the maze problem by using dfs&bfs * author: HP1020--SNOOHAIRY * date: 2019.10.18 -- Firday */ #include #include #include #include "stack_h" #define MAXN 20 void mazePath(int x,int y,int endx,int endy,int n,int m,Stack s); void printPath(Stack s,int n,int m); /* *建立一个二维数组存迷宫 *要是八个方向能有位置则压入栈，要是下一步没有则弹出栈回溯 *直到找到终点为止 */ int direction[8][2]={{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}}; //定义一个数组存八个方向操作数 int maze[MAXN][MAXN]; int flag=0; int main() { int n,m,i,j,xa,xb,ya,yb,ox; //--------------建立迷宫-------------- printf("请输入迷宫大小：（长、宽）\n"); scanf("%d%d",&n,&m); if(n |
【本文地址】
公司简介
联系我们