这篇文章主要介绍了C语言使用深度优先搜索算法解决迷宫问题,涉及C语言堆栈的使用与深度优先算法解决迷宫问题的相关操作技巧,需要的朋友可以参考下
本文实例讲述了C语言使用深度优先搜索算法解决迷宫问题。分享给大家供大家参考，具体如下：
深度优先搜索
伪代码
（Pseudocode）如下：
将起点标记为已走过并压栈; while (栈非空) { 从栈顶弹出一个点p; if (p这个点是终点) break; 否则沿右、下、左、上四个方向探索相邻的点 if (和p相邻的点有<em style="color:transparent">来源[email protected]搞@^&代*@码网</em>路可走，并且还没走过) 将相邻的点标记为已走过并压栈，它的前趋就是p点; } if (p点是终点) { 打印p点的坐标; while (p点有前趋) { p点 = p点的前趋; 打印p点的坐标; } } else 没有路线可以到达终点;
C语言代码：
#include #define MAX_ROW 5 #define MAX_COL 5 struct point { int row, col; } stack[512]; int top = 0; void push(struct point p) { stack[top++] = p; } struct point pop(void) { return stack[--top]; } int is_empty(void) { return top == 0; } int maze[MAX_ROW][MAX_COL] = { 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, }; void print_maze(void) { int i, j; for (i = 0; i <MAX_ROW; i++) { for (j = 0; j <MAX_COL; j++) printf("%d ", maze[i][j]); putchar('\n'); } printf("*********\n"); } struct point predecessor[MAX_ROW][MAX_COL] = { {{-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}}, {{-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}}, {{-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}}, {{-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}}, {{-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}}, }; void visit(int row, int col, struct point pre) { struct point visit_point = { row, col }; maze[row][col] = 2; predecessor[row][col] = pre; push(visit_point); } int main(void) { struct point p = { 0, 0 }; maze[p.row][p.col] = 2; push(p); while (!is_empty()) { p = pop(); if (p.row == MAX_ROW - 1 /* goal */ && p.col == MAX_COL - 1) break; if (p.col+1 = 0 /* left */ && maze[p.row][p.col-1] == 0) visit(p.row, p.col-1, p); if (p.row-1 >= 0 /* up */ && maze[p.row-1][p.col] == 0) visit(p.row-1, p.col, p); print_maze(); } if (p.row == MAX_ROW - 1 && p.col == MAX_COL - 1) { printf("(%d, %d)\n", p.row, p.col); while (predecessor[p.row][p.col].row != -1) { p = predecessor[p.row][p.col]; printf("(%d, %d)\n", p.row, p.col); } } else printf("No path!\n"); return 0; }
希望本文所述对大家C语言程序设计有所帮助。
以上就是C语言使用深度优先搜索算法解决迷宫问题(堆栈)的详细内容，更多请关注gaodaima搞代码网其它相关文章！
搞代码网（gaodaima.com）提供的所有资源部分来自互联网，如果有侵犯您的版权或其他权益，请说明详细缘由并提供版权或权益证明然后发送到邮箱[email protected]，我们会在看到邮件的第一时间内为您处理，或直接联系QQ：872152909。本网站采用BY-NC-SA协议进行授权
转载请注明原文链接：C语言使用深度优先搜索算法解决迷宫问题(堆栈)
转载请注明原文链接：C语言使用深度优先搜索算法解决迷宫问题(堆栈)
