gpt4 book ai didi

C语言使用深度优先搜索算法解决迷宫问题(堆栈)

转载 作者:qq735679552 更新时间:2022-09-28 22:32:09 37 4
gpt4 key购买 nike

CFSDN坚持开源创造价值,我们致力于搭建一个资源共享平台,让每一个IT人在这里找到属于你的精彩世界.

这篇CFSDN的博客文章C语言使用深度优先搜索算法解决迷宫问题(堆栈)由作者收集整理,如果你对这篇文章有兴趣,记得点赞哟.

本文实例讲述了C语言使用深度优先搜索算法解决迷宫问题。分享给大家供大家参考,具体如下:

深度优先搜索 。

C语言使用深度优先搜索算法解决迷宫问题(堆栈)

伪代码 。

(Pseudocode)如下:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
将起点标记为已走过并压栈;
while (栈非空) {
从栈顶弹出一个点p;
if (p这个点是终点)
break;
否则沿右、下、左、上四个方向探索相邻的点
if (和p相邻的点有路可走,并且还没走过)
将相邻的点标记为已走过并压栈,它的前趋就是p点;
}
if (p点是终点) {
打印p点的坐标;
while (p点有前趋) {
p点 = p点的前趋;
打印p点的坐标;
}
} else
没有路线可以到达终点;

C语言代码:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <stdio.h>
#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 < MAX_COL /* right */  && maze[p.row][p.col+1] == 0)
       visit(p.row, p.col+1, p);
     if (p.row+1 < MAX_ROW /* down */ && maze[p.row+1][p.col] == 0)
       visit(p.row+1, p.col, p);
     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语言程序设计有所帮助.

原文链接:http://blog.csdn.net/e421083458/article/details/39185171 。

最后此篇关于C语言使用深度优先搜索算法解决迷宫问题(堆栈)的文章就讲到这里了,如果你想了解更多关于C语言使用深度优先搜索算法解决迷宫问题(堆栈)的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。

37 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com