迷宫问题（C语言实现）（牛客网百度笔试真题）_c语音迷宫问题:可以使用栈或队列实现迷宫问题。基本要求如下:(1) 定义一个二

迷宫问题是一种基础的算法问题，需要通过编程实现在一个迷宫中找到从起点到终点的路线。通常使用深度优先搜索或广度优先搜索算法来解决这个问题（主要是使用递归回溯和栈）

具体步骤如下：

1.定义一个二维数组表示迷宫，其中 0 表示可以通过的路，1 表示障碍物。
2.定义起点和终点坐标。
3.使用深度优先搜索或广度优先搜索算法在迷宫中搜索路径，记录经过的路径。
4.如果搜索到终点，则返回路径，否则返回无解。

代码及注释如下

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
//迷宫问题

//用结构体存迷宫的坐标
typedef struct Maze
{
    int row;
    int col;
}PT;

//由于C语言没有栈的库，所以用‘-’分隔一下栈相关的代码
//-------------------------------------------------------------------
typedef PT Type;//Tpye表示的是PT结构体类型

typedef struct Stack
{
    Type* a;
    int top;//栈顶
    int capacity;//容积
}ST;

void StackInit(ST* ps);
void StackDestory(ST* ps);
//栈顶插入删除数据
//入栈
void StackPush(ST* ps, Type x);
//出栈
void StackPop(ST* ps);

Type StackTop(ST* ps);

int StackSize(ST* ps);
bool StackEmpty(ST* ps);


//初始化
void StackInit(ST* ps)
{
    assert(ps);
    ps->a = (Type*)malloc(sizeof(Type) * 4);
    if (ps->a == NULL)
    {
        printf("扩容失败\n");
        exit(-1);
    }
    ps->capacity = 4;
    ps->top = 0;
}
//销毁
void StackDestory(ST* ps)
{
    assert(ps);
    free(ps->a);
    ps->a = NULL;
    ps->top = ps->capacity = 0;
}

//栈顶插入删除数据
//入栈（插入）
void StackPush(ST* ps, Type x)
{
    assert(ps);
    //满了就增容
    if (ps->top == ps->capacity)
    {
        Type* tmp = realloc(ps->a, ps->capacity * 2 * sizeof(Type));
        if (tmp == NULL)
        {
            printf("扩容失败\n");
            exit(-1);
        }
        else
        {
            ps->a = tmp;
            ps->capacity *= 2;
        }
    }
    ps->a[ps->top] = x;
    ps->top++;

}
//出栈（删除）
void StackPop(ST* ps)
{
    assert(ps);
    //栈空了，直接终止
    assert(ps->top > 0);
    ps->top--;
}
//
Type StackTop(ST* ps)
{
    assert(ps);
    assert(ps->top > 0);
    return ps->a[ps->top - 1];
}
//求数据个数
int StackSize(ST* ps)
{
    assert(ps);
    return ps->top;
}
//
bool StackEmpty(ST* ps)
{
    assert(ps);
    return ps->top == 0;
}

ST path;//定义一个全局的栈，用来存放迷宫路径位置的坐标
//----------------------------------------------------------------------------

//输出坐标
//（由于我们把坐标存入栈时的顺序和题目要求的顺序一样，就会导致出栈时坐标是反着出的
//，因此就需要倒置栈中的元素）【具体操作就看下面的PrintPath函数】
void PrintPath()//由于path是全局变量，就不需要再传参了
{
    //将栈里元素入到另外一个栈里面
    //再输出另外一个栈的元素，就实现了倒置
    ST rpath;//用这个栈来输出
    StackInit(&rpath);//初始化栈
    while (!StackEmpty(&path))//把path中的元素入到rpath中来
    {
        StackPush(&rpath, StackTop(&path));
        StackPop(&path);
    }
    while (!StackEmpty(&rpath))//再输出rpath中的元素，就就实现了倒置
    {
        PT top = StackTop(&rpath);
        printf("(%d,%d)\n", top.row, top.col);
        StackPop(&rpath);
    }
    StackDestory(&rpath);
}

//测试迷宫图是否正确（不写这个函数也行）
void PrintMaze(int** maze, int n, int m)
{
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            printf("%d ", maze[i][j]);
        }
        printf("\n");
    }
}

//判断该位置是否能走
int IsPass(int** maze, int n, int m, PT cur)
{
    //坐标不能越界且该位置值为0
    if (cur.col >= 0 && cur.row >= 0
        && cur.col < m && cur.row < n
        && maze[cur.row][cur.col] == 0)
    {
        return 1;
    }
    else
    {
        return 0;
    }

}

//判断迷宫是否能走到出口（递归回溯）
//（如果该位置能走通，就入栈，走不通（死路），就把该位置坐标弹出栈）
int MazePath(int** maze, int n, int m, PT cur)//cur表示从迷宫走的起始位置坐标
{
    StackPush(&path, cur);//入栈
    //如果走到出口
    if (cur.row == n - 1 && cur.col == m - 1)
    {
        return 1;
    }
    //探测上下左右四个方向
    PT next;//定义一个存放下一个位置坐标的结构变量
    maze[cur.row][cur.col] = 2;//把走过的位置设为2，以防死递归

    //上
    next = cur;
    next.row -= 1;
    //如果下一个位置能走，就递归【上下左右同理】
    if (IsPass(maze, n, m, next))
    {
        if (MazePath(maze, n, m, next))
            return 1;
    }

    //下
    next = cur;
    next.row += 1;
    if (IsPass(maze, n, m, next))
    {
        if (MazePath(maze, n, m, next))
            return 1;
    }
    //左
    next = cur;
    next.col -= 1;
    if (IsPass(maze, n, m, next))
    {
        if (MazePath(maze, n, m, next))
            return 1;
    }
    //右
    next = cur;
    next.col += 1;
    if (IsPass(maze, n, m, next))
    {
        if (MazePath(maze, n, m, next))
            return 1;
    }
    //如果上下左右都不通，就把该位置坐标弹出栈
    StackPop(&path);//出栈
    return 0;
}

int main()
{
    int N = 0;
    int M = 0;

    while (scanf("%d %d", &N, &M) != EOF)
    {
        //动态开辟二维数组
        int** maze = (int**)malloc(sizeof(int*) * N);
        for (int i = 0; i < N; i++)
        {
            maze[i] = (int*)malloc(sizeof(int) * M);
        }
        //输入
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < M; j++)
            {
                scanf("%d", &maze[i][j]);
            }
        }
        StackInit(&path);
        PT str = { 0,0 };
        if (MazePath(maze, N, M, str))
        {
            //找到了
            PrintPath();
        }
        else
        {
            printf("未找到");
        }
        StackDestory(&path);
        for (int i = 0; i < N; i++)
        {
            free(maze[i]);
        }
        free(maze);
        maze = NULL;
    }

    return 0;
}
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

运行结果：

迷宫问题的意义

迷宫问题是一类经典的寻路问题，通常被用来测试和研究搜索算法、路径规划算法和人工智能等方面的技术。在现实生活中，迷宫问题的应用场景非常广泛，例如在物流配送中的路径规划、机器人导航、游戏设计和智力竞赛等方面都有应用。此外，解决迷宫问题可以锻炼人的逻辑思维、学习算法的实现和优化、提高计算机编程能力等。