用栈式随机寻径编写一段迷宫算法

栈式随机寻径算法是一种用于解决迷宫问题的算法，它通过在访问过的路径中存储信息，以便回溯到之前的状态，以便在遇到死胡同时找到出路。具体来说，它的基本思想是从起点出发，沿着当前可能的路径进行搜索，如果遇到死胡同，则回溯到之前的路径，直到找到出路为止。

相关问题

用C语言编写一个随机生成迷宫的代码

好的，下面是一个简单的随机生成迷宫的 C 语言代码：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define ROW 10
#define COL 10

void print_maze(int maze[ROW][COL]) {
    for (int i = 0; i < ROW; i++) {
        for (int j = 0; j < COL; j++) {
            printf("%d ", maze[i][j]);
        }
        printf("\n");
    }
}

void generate_maze(int maze[ROW][COL]) {
    // 初始化迷宫
    for (int i = 0; i < ROW; i++) {
        for (int j = 0; j < COL; j++) {
            maze[i][j] = 1;
        }
    }

    // 随机生成迷宫
    srand(time(NULL));
    int start_row = rand() % ROW;
    int start_col = rand() % COL;
    maze[start_row][start_col] = 0;

    while (1) {
        int row = rand() % ROW;
        int col = rand() % COL;

        if (maze[row][col] == 1) {
            // 判断相邻格子是否已经被打通
            if ((row - 1 >= 0 && maze[row - 1][col] == 0)
                || (row + 1 < ROW && maze[row + 1][col] == 0)
                || (col - 1 >= 0 && maze[row][col - 1] == 0)
                || (col + 1 < COL && maze[row][col + 1] == 0)) {
                maze[row][col] = 0;
            }
        }

        // 判断是否已经生成了迷宫
        int flag = 0;
        for (int i = 0; i < ROW; i++) {
            for (int j = 0; j < COL; j++) {
                if (maze[i][j] == 1) {
                    flag = 1;
                    break;
                }
            }
        }
        if (flag == 0) {
            break;
        }
    }
}

int main() {
    int maze[ROW][COL];
    generate_maze(maze);
    print_maze(maze);
    return 0;
}

这段代码定义了迷宫的行数和列数，然后随机选取一个起点，逐步生成迷宫，最后打印出来。注意，这只是一个简单的示例代码，实际应用中可能需要更复杂的算法和数据结构来生成更有趣的迷宫。

c语言用栈实现迷宫算法

以下是使用栈实现迷宫算法的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，避免重复探索。如果最终到达终点，则输出路径。如果探索完所有可能的位置，仍然没有到达终点，则说明无法找到路径。