C语言实验：迷宫问题（dfs，C语言实现栈）

2021-05-12 05:30

阅读：593

标签：退出 end lib round == sem printf 入栈 pop

Description

给定迷宫起点和终点，寻找一条从起点到终点的路径。

	(0,1)
(2,0)	起点 (1,1)	(1,2)	(1,3)	(1,4)
(2,0)	(2,1)			(2,4)
(3,0)	(3,1)	(3,2)		终点（3,4）
	(4,1)

上图中黄色代表墙，白色代表通路，起点为(1,1)，终点为(3,4)。

要求搜寻策略是从起点开始按照“上、下、左、右”四个方向寻找终点，到下一个点继续按照“上、下、左、右”四个方面寻找，当该结点四个方向都搜寻完，但还没到终点时，退回到上一个点，直到找到终点或者没有路径。

比如上图从(1,1)开始，向上(0,1)不通，向下到(2,1)；到了(2,1)后继续按“上、下、左、右”四个方面寻找，上已经走过，向下到(3,1)；到(3,1)后上已经走过，下和左不通，向右到(3,2)；到(3,2)四个方面都不通，回到(3,1)四个方向都不通，再回到(2,1),(1,1)；到达(1,1)后下已经走过，左不通，继续向右走，重复这个过程最后到达(3,4)。

Input

第一行两个数m和n表示迷宫的行数和列数。迷宫大小不超过100×100

第二行四个数x1,y1,x2,y2分别表示起点和终点的坐标。

接下来是m行n列的数，用来表示迷宫，1表示墙，0表示通路。

Output

从起点到终点所经过的路径的坐标。如果不存在这样的路径则输出“No Path!”。

Sample Input

5 6
1 1 3 4
1 1 1 1 1 1 
1 0 0 0 0 1 
1 0 1 1 0 1
1 0 0 1 0 1
1 1 1 1 1 1

Sample Output

(1 1)(1 2)(1 3)(1 4)(2 4)(3 4)


1.思路：
（1）若当前点是终点，dfs函数返回1；
（2）若不是终点，将此点标记为1，对该点4个方向进行搜索，实现方式为定义int  dir[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} }; 通过一个小循环：
　　for(int i = 0; i 　
  　    position nextp;　　
        nextp.x = dir[i][0] + now.x;
        nextp.y = dir[i][1] + now.y;
            ......
　　}　
 进行搜索；若该点的下一个点nextp不是墙，未走，并且没有超界则将nextp压入栈中，递归调用dfs，若此过程经过（1）判断返回了1，说明最终找到了通往终点的路，便可以返回1，结束函数，此时栈中已储存了通往终点的路径，
 若没有通路，则弹出栈顶元素，根据递归原理该路径上的所有点都会弹出并标记未走，回溯到之前的点，继续向其他方向搜索，直到找到终点或遍历完整个图。
（3）遍历整个图都没有发现通往终点的路，则输出“No Path！”。

2.代码：

 1 #include  2 #include  3 #include string.h>
 4 #include  5 
 6 typedef struct {
 7     int x;
 8     int y;
 9 }position;
10 
11 typedef struct my_stack {
12     int len;
13     position path[10001];//用数组表示栈内元素
14 }Stack;
15 
16 
17 /*栈的实现*/
18 Stack *create_emptystack();
19 int isempty(Stack *s);
20 void push_stack(Stack *s, position pos);
21 void pop_stack(Stack *s);
22 //position get_top(Stack *s);
23 
24 /*dfs*/
25 int judge(position p);
26 int dfs(Stack *s, position now);
27 
28 int a[100][100];
29 position begin, end;
30 int m, n;
31 
32 int main() {
33     scanf("%d%d", &m, &n);
34     scanf("%d%d%d%d", &begin.x, &begin.y, &end.x, &end.y);
35     for(int i = 0; i ) {
36         for(int j = 0; j )
37             scanf("%d", &a[i][j]);
38     }
39     Stack *s = create_emptystack();
40     push_stack(s, begin);
41     dfs(s, begin);
42     if(s->len == 0) printf("No Path!");
43     else for(int i = 0; i len + 1; i++)
44             printf("(%d %d)", s->path[i].x, s->path[i].y);
45     return 0;
46 }
47 
48 Stack* create_emptystack() {
49     Stack *S;
50     S = (Stack*)malloc(sizeof(Stack));
51     if(S == NULL)
52         printf("malloc error\n");
53     else
54         S->len = -1;
55     return S;
56 }
57 
58 int isempty(Stack *s) {
59     return s->len == -1;
60 }
61 
62 void push_stack(Stack *s, position pos) {
63     if(s->len > 10001)
64         printf("exceed!\n");
65     else {
66         s->len++;
67         s->path[s->len] = pos;
68     }
69 }
70 
71 void pop_stack(Stack *s) {
72     if(!isempty(s))
73         s->len--;
74 }
75 
76 //position get_top(Stack *s) {return s->path[s->len];}
77 
78 int judge(position p) {
79     return a[p.x][p.y] == 0 && p.x >= 0 && p.x = 0 && p.y //没有走并且没有超界
80 }
81 
82 int dfs(Stack *s, position now) {
83     int dir[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} }; //上下左右四个方向
84     if(now.x == end.x && now.y == end.y) return 1; //如果当前节点是终点, 返回1
85     else{
86         a[now.x][now.y] = 1; //标记已走
87         for(int i = 0; i 4; i++) {
88             position nextp;
89             nextp.x = dir[i][0] + now.x;
90             nextp.y = dir[i][1] + now.y;
91             if(!judge(nextp)) continue; //如果下一个节点不合法, 那么直接退出
92             push_stack(s, nextp); //先把下一个节点压入
93             if(dfs(s, nextp)) return 1; //如果子节点中最终可以找到终点, 那么直接结束
94             pop_stack(s); //如果不能, 那么把下一个节点弹出, 并且进行下一个循环
95         }
96         a[now.x][now.y] = 0;
97         return 0; //如果找不到, 那么直接返回0
98     }
99 }

本题的要点是给dfs函数设置返回值来表示是否有到终点的通路。

C语言实验：迷宫问题（dfs，C语言实现栈）

标签：退出 end lib round == sem printf 入栈 pop

原文地址：https://www.cnblogs.com/knightoflake/p/13143303.html

上一篇：c++类的实例化，有没有new的区别

下一篇：JavaScript返回到上一页的三种方法

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：C语言实验：迷宫问题（dfs，C语言实现栈）
文章链接：http://soscw.com/index.php/essay/84558.html

亲，登录后才可以留言！

C语言实验：迷宫问题（dfs，C语言实现栈）

Description

Input

Output

Sample Input

Sample Output

评论

热门文章

推荐文章

最新文章

置顶文章