• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

C语言实验:迷宫问题(搜索,C语言实现栈、队列)

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

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

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

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

接下来是mn列的数,用来表示迷宫,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 < 4; 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 <stdio.h>
 2 #include <stdlib.h>
 3 #include <string.h>
 4 #include <math.h>
 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 < m; i++) {
36         for(int j = 0; j < n; 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 < s->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 < m && p.y >= 0 && p.y < n; //没有走并且没有超界
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函数设置返回值来表示是否有到终点的通路。

3.最短路径(bfs):

 

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 #include <string.h>
  4 #include <math.h>
  5 
  6 typedef struct {
  7     int x;
  8     int y;
  9     int pre; //记录该结点的父结点(来源)
 10 }position;
 11 
 12 typedef struct my_queue {
 13     position *que;
 14     int front;
 15     int last;
 16 }Queue;
 17 
 18 Queue* create_emptyqueue();
 19 int isempty(Queue *q);
 20 void push_queue(Queue *q, position x);
 21 void pop_queue(Queue *q);
 22 
 23 int a[100][100];
 24 Queue *bfs(position st);
 25 void print(Queue *q, position ans);
 26 
 27 position begin, end;
 28 int m, n, flag = 0;
 29 
 30 
 31 int main() {
 32     int i, j;
 33     Queue *q;
 34     scanf("%d%d", &m, &n);
 35     scanf("%d%d%d%d", &begin.x, &begin.y, &end.x, &end.y);
 36     begin.pre = -1;
 37     for(i = 0; i < m; i++) {
 38         for(j = 0; j < n; j++)
 39             scanf("%d", &a[i][j]);
 40     }
 41     q = bfs(begin);
 42     if(!flag) printf("No Path!");
 43     else {
 44         print(q, q->que[q->front - 1]);
 45         printf("(%d %d)", end.x, end.y);
 46     }
 47     return 0;
 48 }
 49 
 50 Queue *create_emptyqueue() {
 51     Queue *p;
 52     p = (Queue*)malloc(sizeof(Queue));
 53     if(p != NULL) {
 54         p->que = (position*)malloc(10000*sizeof(position));
 55         if(p->que != NULL) {
 56             p->front = 0;
 57             p->last = 0;
 58             return p;
 59         }
 60         else free(p);
 61     }
 62     return NULL;
 63 }
 64 
 65 int isempty(Queue *q) {
 66     return q->front == q->last;
 67 }
 68 
 69 void push_queue(Queue *q, position x) {
 70     if(q->last + 1 == q->front)
 71         printf("full\n");
 72     else {
 73         q->que[q->last] = x;
 74         q->last = q->last + 1;
 75     }
 76 }
 77 
 78 void pop_queue(Queue *q) {
 79     if(q->front == q->last)
 80         printf("empty\n");
 81     else
 82         q->front = q->front + 1;
 83 }
 84 
 85 Queue *bfs(position st) {
 86     int pr, i;
 87     int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
 88     position former, latter;
 89     position t;
 90     Queue *q = create_emptyqueue();
 91     former = st;
 92     push_queue(q, former);
 93     a[former.x][former.y] = 1;
 94     while(!isempty(q)) { //队列不为空,说明可能还有可走的路
 95         latter = q->que[q->front];
 96         pr = q->front;
 97         pop_queue(q);
 98         for(i = 0; i < 4; i++) {
 99             t.x = latter.x + dir[i][0];
100             t.y = latter.y + dir[i][1];
101             t.pre = pr; //记录该结点的来源
102             if(t.x == end.x && t.y == end.y) {
103                 flag = 1;
104                 return q;
105             }
106             if(!a[t.x][t.y] && t.x >= 0 && t.x < m && t.y >= 0 && t.y < n) {
107                 push_queue(q, t);
108                 a[t.x][t.y] = 1;
109             }
110         }
111     }
112     return q;
113 }
114 
115 void print(Queue *q, position ans) { //递归输出
116     if(ans.pre == -1) {
117         printf("(%d %d)", ans.x, ans.y);
118         return ;
119     }
120     else {
121         print(q, q->que[ans.pre]);
122         printf("(%d %d)", ans.x, ans.y);
123     }
124 }

 

 

 

 

鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
设计模式--MVC(C++版)发布时间:2022-07-14
下一篇:
Win10C盘根目录权限发布时间:2022-07-14
热门推荐
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap