数据与结构,C语言,使用栈来完成迷宫问题
时间: 2024-01-22 15:21:20 浏览: 25
迷宫问题可以通过深度优先搜索算法(DFS)来解决,而使用栈可以实现DFS算法。
具体步骤如下:
1. 定义迷宫地图的数据结构,通常使用二维数组来表示,0表示可以通过,1表示障碍物。
2. 定义栈的数据结构,可以使用数组或链表来实现。
3. 从起点开始,将起点压入栈中。
4. 不断取出栈顶元素,检查是否为终点,若是则输出路径,结束程序。
5. 若不是,则将栈顶元素的所有相邻节点(即上下左右四个方向)依次压入栈中,同时在地图上标记已经走过的节点。
6. 重复第4步。
代码实现如下:
```c
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define ROW 6
#define COL 6
int map[ROW][COL] = {
{0, 1, 1, 1, 1, 1},
{0, 0, 0, 0, 1, 1},
{1, 0, 1, 0, 1, 1},
{1, 0, 0, 0, 0, 1},
{1, 1, 1, 1, 0, 0},
{1, 1, 1, 1, 1, 0}
};
struct Node {
int row;
int col;
};
struct Stack {
struct Node data[ROW * COL];
int top;
};
void initStack(struct Stack *s) {
s->top = -1;
}
bool isStackEmpty(struct Stack *s) {
return s->top == -1;
}
bool isStackFull(struct Stack *s) {
return s->top == ROW * COL - 1;
}
void push(struct Stack *s, struct Node n) {
if (isStackFull(s)) {
printf("Stack is full\n");
exit(1);
}
s->data[++s->top] = n;
}
struct Node pop(struct Stack *s) {
if (isStackEmpty(s)) {
printf("Stack is empty\n");
exit(1);
}
return s->data[s->top--];
}
void printPath(struct Stack *s) {
printf("Path: ");
for (int i = 0; i <= s->top; i++) {
printf("(%d, %d) ", s->data[i].row, s->data[i].col);
}
printf("\n");
}
bool isEnd(int row, int col) {
return row == ROW - 1 && col == COL - 1;
}
bool canMove(int row, int col) {
return row >= 0 && row < ROW && col >= 0 && col < COL && map[row][col] == 0;
}
void maze() {
struct Stack s;
initStack(&s);
struct Node start = {0, 0};
push(&s, start);
map[start.row][start.col] = 2;
while (!isStackEmpty(&s)) {
struct Node cur = pop(&s);
if (isEnd(cur.row, cur.col)) {
printPath(&s);
return;
}
struct Node next[4] = {
{cur.row, cur.col + 1},
{cur.row + 1, cur.col},
{cur.row, cur.col - 1},
{cur.row - 1, cur.col}
};
for (int i = 0; i < 4; i++) {
if (canMove(next[i].row, next[i].col)) {
push(&s, next[i]);
map[next[i].row][next[i].col] = 2;
}
}
}
printf("No path found\n");
}
int main() {
maze();
return 0;
}
```
在这个例子中,我们使用了一个二维数组`map`来表示迷宫的地图,1表示障碍物,2表示已经走过的节点。我们使用了一个栈来存储路径节点,每次取出栈顶元素并检查是否为终点,若不是则将栈顶元素的相邻节点压入栈中,并在地图上标记已经走过的节点。如果没有找到路径,则输出“No path found”。