c语言用栈实现迷宫算法
时间: 2023-12-25 17:52:38 浏览: 94
以下是使用栈实现迷宫算法的C语言代码:
```
#include <stdio.h>
#include <stdlib.h>
#define MAZE_SIZE 6
int maze[MAZE_SIZE][MAZE_SIZE] = {
{0, 0, 0, 0, 0, 0},
{0, 1, 1, 0, 1, 0},
{0, 0, 1, 0, 0, 0},
{0, 1, 0, 1, 1, 0},
{0, 1, 0, 0, 1, 0},
{0, 1, 0, 0, 0, 0}
};
typedef struct {
int x;
int y;
} Position;
typedef struct {
Position data[MAZE_SIZE * MAZE_SIZE];
int top;
} Stack;
void init(Stack *stack) {
stack->top = -1;
}
void push(Stack *stack, Position pos) {
if (stack->top == MAZE_SIZE * MAZE_SIZE - 1) {
printf("Stack overflow!\n");
exit(1);
}
stack->data[++stack->top] = pos;
}
Position pop(Stack *stack) {
if (stack->top == -1) {
printf("Stack underflow!\n");
exit(1);
}
return stack->data[stack->top--];
}
int is_empty(Stack *stack) {
return stack->top == -1;
}
void print_path(Stack *stack) {
for (int i = 0; i <= stack->top; i++) {
printf("(%d,%d) ", stack->data[i].x, stack->data[i].y);
}
printf("\n");
}
void maze_path(Position start, Position end) {
Stack stack;
init(&stack);
push(&stack, start);
maze[start.x][start.y] = -1;
while (!is_empty(&stack)) {
Position cur = pop(&stack);
if (cur.x == end.x && cur.y == end.y) {
print_path(&stack);
return;
}
if (cur.x > 0 && maze[cur.x - 1][cur.y] == 0) {
Position next = {cur.x - 1, cur.y};
push(&stack, next);
maze[next.x][next.y] = -1;
}
if (cur.x < MAZE_SIZE - 1 && maze[cur.x + 1][cur.y] == 0) {
Position next = {cur.x + 1, cur.y};
push(&stack, next);
maze[next.x][next.y] = -1;
}
if (cur.y > 0 && maze[cur.x][cur.y - 1] == 0) {
Position next = {cur.x, cur.y - 1};
push(&stack, next);
maze[next.x][next.y] = -1;
}
if (cur.y < MAZE_SIZE - 1 && maze[cur.x][cur.y + 1] == 0) {
Position next = {cur.x, cur.y + 1};
push(&stack, next);
maze[next.x][next.y] = -1;
}
}
printf("No path found!\n");
}
int main() {
Position start = {1, 1};
Position end = {4, 4};
maze_path(start, end);
return 0;
}
```
该算法使用深度优先搜索,从起点开始,逐步向四个方向探索,如果遇到墙壁或已经探索过的位置,则返回上一步继续探索。将已经探索过的位置标记为-1,避免重复探索。如果最终到达终点,则输出路径。如果探索完所有可能的位置,仍然没有到达终点,则说明无法找到路径。
阅读全文