数据结构：迷宫_迷宫问题。假设迷宫由m行n列构成,有一个入口和一个出口,入口坐标为(1,1),出口

迷宫问题。假设迷宫由m行n列构成，有一个入口和一个出口，入口坐标为（1，1），出口坐标为（m，n），试设计并验证以下算法：找出一条从入口通往出口的路径，或报告一个“无法通过”的信息。

(1) 用C语言实现顺序存储结构上队列的基本操作，然后利用该队列的基本操作找出迷宫的一条最短路径。

(2) 设计一个二维数组MAZE[m+2][n+2]表示迷宫，数组元素为0表示该位置可以通过，数组元素为1表示该位置不可以通行。MAZE[1][1]、MAZE[m][n]分别为迷宫的入口和出口。

(3) 输入迷宫的大小m行和n列，动态生成二维数组；由随机数产生0或1，建立迷宫，注意m*n的迷宫需要进行扩展，扩展部分的元素设置为1，相当于在迷宫周围布上一圈不准通过的墙。

(4) 要求输出模拟迷宫的二维数组；若存在最短路经，则由出口回溯到入口（出队列并利用栈实现），再打印从入口到出口的这条路径，例如(1,1)，……，(i,j)，……，(m,n)；若没有路径，则打印“No path!”。

(5)迷宫的任一位置(i,j)上均有四个可以移动的方向，用二维数组Direction存放八个方向上的位置偏移量。

Direction[8][2]={{0,1},{1,1},{0,-1},{-1,-1},{1,1},{0,-1},{-1,-1},{0,1}};

(6)为避免出现原地踏步的情况为了标志已经通过的位置，采用一个标志数组MARK[m+2][n+2]，初值均为0，在寻找路径的过程中，若通过了位置(i,j)，则将MARK[i][j]置为1。

(7) 为了记录查找过程中到达位置(i,j)及首次到达(i,j)的前一位置(i_pre,j_pre)，需要记住前一位置(i_pre,j_pre)在队列中的序号pre，即队列中数据元素应该是一个三元组(i,j,pre)。

(8) 搜索过程简单描述如下：将入口MAZE[1][1]作为第一个出发点，依次在八个方向上搜索可通行的位置，将可通行位置(i,j,pre)入队，形成第一层新的出发点，然后依次出队，即对第一层中各个位置分别搜索它所在八个方向上的可通行位置，形成第二层新的出发点，…，如此进行下去，直至达到出口MAZE[m][n]或者迷宫所有位置都搜索完毕为止。

注意：迷宫元素我是根据书上的一个迷宫图创建的，具体要以实际图为准。

//
// Created by CHAO on 2021-11-06.
//

#include "stdio.h"
#include "stdlib.h"
typedef struct table{   //迷宫元素
    int x;  //坐标
    int y;
    int status; //状态
    int foot;
    struct table *next;
    struct table *before;
}Table;

typedef struct Quene{        //队列链表
    Table *head;
    Table *wei;
}quene;

quene *create(){   //创建空队列

    quene *s;
    s=(quene *) malloc(sizeof (quene));
    s->head=(Table *) malloc(sizeof (Table));
    s->wei=s->head;
    if(!s->head)
        exit(0);
    s->head->next=s->wei->next=NULL;
    return s;
}


void delete(quene *s){      //删除队列头元素

    if(s->wei==s->head)
    {
        printf("队列中无元素\n");
        exit(0);
    }
    if(s->head->next==s->wei) {
        s->head = s->wei;
        s->head->next=NULL;
    }
   else {
        Table *p;
        p = s->head->next;
        s->head->next = p->next;
        free(p);
    }

}

void addquene(quene *s,Table a){    //添加元素到队列

    Table *p;
    p=(Table *) malloc(sizeof (Table));
    if(!p)
        exit(0);
    p->x=a.x;
    p->y=a.y;
    p->status=a.status;
    p->next=NULL;
    s->wei->next=p;
    s->wei=p;
}

void addquene2(quene *s,Table  b,Table a){    //添加元素到队列

    Table *p;
    Table *q;
    p=(Table *) malloc(sizeof (Table));
    if(!p)
        exit(0);
    p->x=a.x;
    p->y=a.y;
    p->next=NULL;
    s->wei->next=p;
    s->wei=p;
    //遍历队列，找出前驱
    q=s->head->next;
    while (q){
        if(q->x==b.x && q->y==b.y)
        {
            s->wei->before=q;
            break;
        }
        else
        {
            q=q->next;
        }
    }

}


void pri(quene *s){ //打印

    Table *p;
    if(s->head==s->wei)
    {
        printf("队列元素为空\n");
        return;
    }
    else {
        p = s->head->next;
        while (p) {
            printf("坐标为 %d,%d\n", p->x, p->y);
            p = p->next;
        }
    }
}

void pri2(quene *s){


    Table *p;
    if(s->head==s->wei)
    {
        printf("队列元素为空\n");
        return;
    }
    else {
        p = s->head->next;
        while (p->x!=8||p->y!=8)
            p=p->next;
            while (p != s->head) {
                printf("坐标为 %d,%d\n", p->x, p->y);
                p = p->before;
            }
    }
}


void crgong(quene *quene1){   //迷宫初始化，以及走迷宫

    //quene2存放实际迷宫路径
    quene *quene2;
    quene2=create();

    Table gong[10][10];
    for(int i=0;i<10;i++){
        for(int j=0;j<10;j++){
            gong[i][j].status=1;
            gong[i][j].foot=0;
        }
    }
    for(int i=0;i<10;i++){
        gong[0][i].x=i;
        gong[0][i].y=0;
        gong[0][i].status=0;
    }
    for(int i=0;i<10;i++){
        gong[9][i].x=i;
        gong[9][i].y=0;
        gong[9][i].status=0;
    }
    for(int i=0;i<10;i++){
        gong[i][0].x=i;
        gong[i][0].y=0;
        gong[i][0].status=0;
    }
    for(int i=0;i<10;i++){
        gong[i][9].x=i;
        gong[i][9].y=0;
        gong[i][9].status=0;
    }
    gong[1][3].x=1;gong[1][3].y=3;gong[1][3].status=0;
    gong[2][3].x=2;gong[2][3].y=3;gong[2][3].status=0;
    gong[1][7].x=1;gong[1][7].y=7;gong[1][7].status=0;
    gong[2][7].x=2;gong[2][7].y=7;gong[2][7].status=0;
    gong[3][5].x=3;gong[3][5].y=5;gong[3][5].status=0;
    gong[3][6].x=3;gong[3][6].y=6;gong[3][6].status=0;
    gong[4][2].x=4;gong[4][2].y=2;gong[4][2].status=0;
    gong[4][3].x=4;gong[4][3].y=3;gong[4][3].status=0;
    gong[4][4].x=4;gong[4][4].y=4;gong[4][4].status=0;
    gong[5][4].x=5;gong[4][2].y=4;gong[5][4].status=0;
    gong[6][2].x=6;gong[6][2].y=2;gong[6][2].status=0;
    gong[6][6].x=6;gong[6][6].y=6;gong[6][6].status=0;
    gong[7][2].x=7;gong[7][2].y=2;gong[7][2].status=0;
    gong[7][3].x=7;gong[7][3].y=3;gong[7][3].status=0;
    gong[7][4].x=7;gong[7][4].y=4;gong[7][4].status=0;
    gong[7][6].x=7;gong[7][6].y=6;gong[7][6].status=0;
    gong[7][7].x=7;gong[7][7].y=7;gong[7][7].status=0;
    gong[8][1].x=8;gong[8][1].y=1;gong[8][1].status=0;
    gong[8][4].status=0;

    for(int i=1;i<=7;i++){
        gong[i][1].x=i;
        gong[i][1].y=1;
    }
    for(int i=1;i<=8;i++){
        gong[i][8].x=i;
        gong[i][8].y=8;
    }
    for(int i=4;i<=8;i++){
        gong[i][5].x=i;
        gong[i][5].y=5;
    }
    for(int i=3;i<=6;i++){
        gong[i][7].x=i;
        gong[i][7].y=7;
    }
    gong[1][2].x=1;gong[1][2].y=2;
    gong[2][2].x=2;gong[2][2].y=2;
    gong[3][2].x=3;gong[3][2].y=2;
    gong[5][2].x=5;gong[5][2].y=2;
    gong[8][2].x=8;gong[8][2].y=2;
    gong[3][3].x=3;gong[3][3].y=3;
    gong[5][3].x=5;gong[5][3].y=3;
    gong[6][3].x=6;gong[6][3].y=3;
    gong[8][3].x=8;gong[8][3].y=3;
    gong[1][4].x=1;gong[1][4].y=4;
    gong[2][4].x=2;gong[2][4].y=4;
    gong[3][4].x=3;gong[3][4].y=4;
    gong[6][4].x=6;gong[6][4].y=4;
    gong[8][4].x=8;gong[8][4].y=4;
    gong[1][5].x=1;gong[1][5].y=5;
    gong[2][5].x=2;gong[2][5].y=5;
    gong[1][6].x=1;gong[1][6].y=6;
    gong[2][6].x=2;gong[2][6].y=6;
    gong[4][6].x=4;gong[4][6].y=6;
    gong[5][6].x=5;gong[5][6].y=6;
    gong[8][6].x=8;gong[8][6].y=6;
    gong[8][7].x=8;gong[8][7].y=7;
    gong[8][8].status=2;


    addquene(quene1,gong[1][1]);    //添加入口
    gong[1][1].foot=1;
    addquene(quene2,gong[1][1]);
    quene2->head->next->before=NULL;
    while(quene1->head!=quene1->wei){       //循环

        //添加探索方向
        int t1=quene1->head->next->x;
        int t2=quene1->head->next->y;
        printf("目前走到的位置的坐标为 %d,%d\n",t1,t2);

        if(t1==8&&t2==8)
        {
            printf("走出迷宫\n");
            break;
        }

        if(gong[t1][t2+1].status!=0&&gong[t1][t2+1].foot==0)    //添加右侧方向
        {
            addquene(quene1,gong[t1][t2+1]);
            gong[t1][t2+1].foot=1;
            addquene2(quene2,gong[t1][t2],gong[t1][t2+1]);    //添加到走出迷宫的路径队列中
        }
        if(gong[t1+1][t2].status!=0&&gong[t1+1][t2].foot==0) {  //添加下方方向
            addquene(quene1, gong[t1 + 1][t2]);
            gong[t1 + 1][t2].foot=1;
            addquene2(quene2,gong[t1][t2],gong[t1+1][t2]);
        }
        if(gong[t1][t2-1].status!=0&&gong[t1][t2-1].foot==0)    //添加左侧方向
        {
            addquene(quene1,gong[t1][t2-1]);
            gong[t1][t2-1].foot=1;
            addquene2(quene2,gong[t1][t2],gong[t1][t2-1]);
        }
        if(gong[t1-1][t2].status!=0&&gong[t1-1][t2].foot==0)    //添加上方方向
        {
            addquene(quene1,gong[t1-1][t2]);
            gong[t1-1][t2].foot=1;
            addquene2(quene2,gong[t1][t2],gong[t1-1][t2]);
        }

        delete(quene1);
    }
    printf("实际走出迷宫的路线为：\n");
    pri2(quene2);

}

void main(){
    quene *quene1=create();
    printf("空队列创建完成\n");
    crgong(quene1);
}
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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281

迷宫走法是水波法，走到哪里就把4个方向都添加到队列中，当然添加之前要判断是否走过了，是否为石头（status=0）。

现在打印实际走的路线