把这个迷宫问题代码修改一下

Question

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <Windows.h>
#define M 100
#define N 100
int Direction[4][2]={{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1}};//代表八个方向的位移偏量

typedef struct {//结点元素结构体
    int x;//代表某个点坐标x
    int y;//代表某个点坐标y
    int pre;//代表某点的前驱结点在队列中的下标
}node;

typedef struct {//顺序栈的定义
    node *elem;
    int size;
    int top;
}MyStack;

typedef struct {//顺序队列的定义
    node *node;
    int rear;
    int front;
}MyQueue;

void color(int x);//改变打印出颜色的函数
void InPutMaze(int maze[][N],int m,int n);//自动创建迷宫的函数
void OutPutMaze( int MAZE[][N],int m,int n);//输出迷宫的函数
MyStack *StackCreak(MyStack *stack);//栈的创建
MyQueue *QueueCreak(MyQueue *queue);//队列的创建
void PushStack(MyStack *stack,int x,int y,int pre);//入栈操作
void PopStack(MyStack *stack);//出栈操作
int StackEmpty(MyStack *stack);//判断栈是否为空
node GetStackTop(MyStack *stack);//获取栈顶元素
void PushQueue(MyQueue *queue,int x,int y,int pre);//入队操作
void OutQueue(MyQueue *queue);//出队操作
node GetQueueHead(MyQueue *queue);//获取队头元素
int QueueEmpty(MyQueue *queue);//判断队列是否为空
void PrintPath(MyStack *myStack,int MAZE[][N]);//打印出路径
void FindPath(MyQueue *queue,MyStack *stack,int sx,int sy,int MAZE[][N],int MARK[][N],int m,int n);//找到路径

int main() {
    int m;
    int n;
    printf("请依次输入迷宫的m和n\n");
    printf("迷宫的大小为m+2 * n+2\n");
    scanf("%d %d",&m,&n);
    int MAZE[M][N];
    int MARK[M][N];
    int i,j;
    for( i = 0;i < m+2;i++){
        for( j = 0; j < n+2;j++){
            MARK[i][j] = 0;
        }
    }
    InPutMaze(MAZE,m,n);//自动生成迷宫
    OutPutMaze(MAZE,m,n);//先打印出迷宫的样子
    MyStack *stack = StackCreak(stack);//创建栈
    MyQueue *queue = QueueCreak(queue);//创建队列
    PushStack(stack,2,2,2);//由于遍历的需要，栈会有个多余元素，其本身不会影响结果，不加的话才会
    FindPath(queue,stack,1,1,MAZE,MARK,m,n);//捕捉路径，传入的参数依次为，队列，栈，起点坐标，迷宫，标记数组，迷宫行列（迷宫终点与其相关）
    PrintPath(stack,MAZE);//打印出路径
    OutPutMaze(MAZE,m,n);//输出操作后迷宫
    return 0;
}

void OutPutMaze( int MAZE [][N],int m,int n)
 {int i,j;
    for( i = 0; i < m + 2; i++){//以二重循环遍历二维数组中的每个元素打印
        for( j = 0;j < n+2;j++){
            if(MAZE[i][j] == 0){//对于0即可通结点用‘3’颜色，下面原理相同
                color(3);
                printf("%d ",MAZE[i][j]);
            }
            else if(MAZE[i][j] == 1)
            {
                color(4);
                printf("%d ",MAZE[i][j]);
            }
            else if(MAZE[i][j] == 2){
                color(6);
                printf("%d ",MAZE[i][j]);
            }
        }
        printf("\n");
    }
}

void InPutMaze(int maze[][N],int m,int n){//随机生成一个迷宫
    srand((unsigned)time(NULL));
    int i,j;
    for(i = 0;i < m+2;i++){
        for( j = 0; j < n+2;j++){
            if(i == 0 || j == 0 || i == m+1 || j == n+1)//判断某个坐标点是否为边界点，是的话赋值为1
                maze[i][j] = 1;
            else
                maze[i][j] = rand()%2;//对随机数除2取余即可获得随机的0或1
        }
    }
    maze[1][1] = 0;//起点和终点赋值为0
    maze[m][n] = 0;
}

MyStack *StackCreak(MyStack *stack){//栈的初始化操作
    stack = malloc(sizeof (MyStack));
    stack->elem = malloc(sizeof (node) * 10000);//申请足够大的空间避免溢出
    stack->top = 0;
    stack->size = 1;
    return stack;//返回该指针
}

void PushStack(MyStack *stack,int x,int y,int pre){//入栈操作，栈中每个元素都是一个结构体结点
    stack->size++;
    stack->elem[stack->top].x = x;
    stack->elem[stack->top].y = y;
    stack->elem[stack->top].pre = pre;
    stack->top++;
}

void PopStack(MyStack *stack){//出栈操作
    stack->top--;
}

node GetStackTop(MyStack *stack){//获取栈顶元素
    node node1;//返回的是一个结构体结点
    node1.x = stack->elem[stack->top-1].x;
    node1.y = stack->elem[stack->top-1].y;
    node1.pre = stack->elem[stack->top-1].pre;
    return node1;
}

int StackEmpty(MyStack *stack){//判断栈是否为空
    if(stack->top == 0)
        return 1;
    return 0;
}

MyQueue *QueueCreak(MyQueue *queue){//队列的初始化
    queue = malloc(sizeof (MyQueue));
    queue->node = malloc(sizeof (node) * 10000);//也需要申请足够大的空间
    queue->front = 0;
    queue->rear = 0;
    return queue;
}

void PushQueue(MyQueue *queue,int x,int y,int pre){//入队操作
    queue->node[queue->rear].x = x;//让rear往后移动即可
    queue->node[queue->rear].y = y;
    queue->node[queue->rear].pre = pre;
    queue->rear++;
}

void OutQueue(MyQueue *queue){//出队操作，让front向后偏移
    queue->front++;
}

node GetQueueHead(MyQueue *queue){//获取队头元素
    node node1;//返回对头的坐标及父亲的下标
    node1.x = queue->node[queue->front].x;
    node1.y = queue->node[queue->front].y;
    node1.pre = queue->node[queue->front].pre;
    return node1;
}

int QueueEmpty(MyQueue *queue){//判断队列是否为空
    if(queue->rear == queue->front)
        return 1;
    return 0;
}

void FindPath(MyQueue *queue,MyStack *stack,int sx,int sy,int MAZE[][N],int MARK[][N],int m,int n){//捕捉路径
    node Gather;//先引入一个结构体变量和三个整形的
    int tx;
    int ty;
    PushQueue(queue,sx,sy,-1);//将起点入队和入栈，由于其没有父亲，可将pre定义为-1，其实可以任意定义一个小于1的数字
    PushStack(stack,sx,sy,-1);
    int find = 0;//代表是否搜索到终点
    while (!QueueEmpty(queue) && !find){//循环的结束条件是队列为空或者已经捕获到终点
        Gather = GetQueueHead(queue);//获取队头元素
        OutQueue(queue);//队头结点出队
        int now = queue->front;//队头元素的下标
        int k;
        for( k = 0;k < 8;k++){//遍历八次即搜索八个方向
            tx = Gather.x + Direction[k][0];//加上特定二维数组完成对八个方向的搜索
            ty = Gather.y + Direction[k][1];
            if(tx < 1 || tx > m || ty < 1 || ty > n){//判断搜索到的是否是边界
                continue;
            }
            if(MAZE[tx][ty] == 0 && MARK[tx][ty] == 0){//如果其在迷宫上为0且没有在标记数组中出现（即没有被走过）那么纳入队列和栈
                MARK[tx][ty] = 1;
                PushQueue(queue,tx,ty,now);
                PushStack(stack,tx,ty,now);
            }
            if(tx == m && ty == n){//如果捕获到终点则结束
                find = 1;
                break;
            }
        }
    }

    if(find == 0){//如果上面的操作并没有找到终点则打印如下并退出
        printf("NO PATH!");
        exit(-1);
    }
}

void PrintPath(MyStack *myStack,int MAZE[][N]){//打印地图操作
    printf("\n");
    printf("路径(从右到左):");//由于是栈的操作所以打印出的是终点到起点
    int target = myStack->elem[myStack->top-1].pre;//如果有通路，那么栈顶元素一定是终点，pre为该点父亲的下标也等于其父亲的top-1
    MAZE[GetStackTop(myStack).x][GetStackTop(myStack).y] = 2;//把最短路径赋值为2方便观察
    printf("(");
    printf("%d,%d",myStack->elem[myStack->top-1].x,myStack->elem[myStack->top-1].y);//先打印出终点
    printf(") ");
    while (!StackEmpty(myStack)){//循环结束即出栈完成
        if(myStack->top-1 == target){//如果出栈元素的top-1也就是其下标等于上一次被打印元素的pre，则证明是上一个被打印元素的父亲
            printf("<- (");
            printf("%d,%d",myStack->elem[myStack->top-1].x,myStack->elem[myStack->top-1].y);
            printf(") ");
            target = myStack->elem[myStack->top-1].pre;//target改变，因为已经又找到一个路径元素
            MAZE[GetStackTop(myStack).x][GetStackTop(myStack).y] = 2;
            PopStack(myStack);//出栈
        }
        else{//如果不是其父亲直接出栈
            PopStack(myStack);
        }
    }
    printf("\n\n");
}

void color(int x) {//一个可以自由选打印颜色的方法
    SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), x);
}

修改成只能上下左右四个方向形成路径，并且每次随机生成迷宫至少存在一条路径的迷宫，其他的不变

Answer 1

只需要4个方向就行了，我还是一名小学生，希望多多支持

```c++
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <Windows.h>

#define M 100
#define N 100

int Direction[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 代表上下左右四个方向的位移偏量

typedef struct // 结点元素结构体
{
    int x;    // 代表某个点坐标x
    int y;    // 代表某个点坐标y
    int pre;  // 代表某点的前驱结点在队列中的下标
} node;

typedef struct // 顺序栈的定义
{
    node *elem;
    int size;
    int top;
} MyStack;

typedef struct // 顺序队列的定义
{
    node *node;
    int rear;
    int front;
} MyQueue;

void color(int x); // 改变打印出颜色的函数
void InPutMaze(int maze[][N], int m, int n); // 自动创建迷宫的函数
void OutPutMaze(int MAZE[][N], int m, int n); // 输出迷宫的函数
MyStack *StackCreate(); // 栈的创建
MyQueue *QueueCreate(); // 队列的创建
void PushStack(MyStack *stack, int x, int y, int pre); // 入栈操作
void PopStack(MyStack *stack); // 出栈操作
int StackEmpty(MyStack *stack); // 判断栈是否为空
node GetStackTop(MyStack *stack); // 获取栈顶元素
void PushQueue(MyQueue *queue, int x, int y, int pre); // 入队操作
void OutQueue(MyQueue *queue); // 出队操作
node GetQueueHead(MyQueue *queue); // 获取队头元素
int QueueEmpty(MyQueue *queue); // 判断队列是否为空
void PrintPath(MyStack *myStack, int MAZE[][N]); // 打印出路径
void FindPath(MyQueue *queue, MyStack *stack, int sx, int sy, int MAZE[][N], int MARK[][N], int m, int n); // 找到路径

int main()
{
    int m;
    int n;
    printf("请依次输入迷宫的m和n\n");
    printf("迷宫的大小为m+2 * n+2\n");
    scanf("%d %d", &m, &n);
    int MAZE[M][N];
    int MARK[M][N];
    int i, j;
    for (i = 0; i < m + 2; i++)
    {
        for (j = 0; j < n + 2; j++)
        {
            MARK[i][j] = 0;
        }
    }
    InPutMaze(MAZE, m, n); // 自动生成迷宫
    OutPutMaze(MAZE, m, n); // 先打印出迷宫的样子
    MyStack *stack = StackCreate(); // 创建栈

    MyQueue *queue = QueueCreate(); // 创建队列
    int sx, sy; // 起始点坐标
    printf("请输入起始点坐标（x, y）：\n");
    scanf("%d %d", &sx, &sy);
    FindPath(queue, stack, sx, sy, MAZE, MARK, m, n); // 找到路径
    PrintPath(stack, MAZE); // 打印路径
    return 0;
}

void color(int x)
{
    SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), x); // 改变控制台字体颜色
}

void InPutMaze(int maze[][N], int m, int n)
{
    srand((unsigned)time(NULL));
    int i, j;
    for (i = 0; i < m + 2; i++)
    {
        for (j = 0; j < n + 2; j++)
        {
            if (i == 0 || i == m + 1 || j == 0 || j == n + 1)
                maze[i][j] = 1; // 将迷宫的外围置为1，表示墙壁
            else
                maze[i][j] = rand() % 2; // 随机生成迷宫内部的0和1，0表示通路，1表示墙壁
        }
    }
}

void OutPutMaze(int MAZE[][N], int m, int n)
{
    int i, j;
    for (i = 0; i < m + 2; i++)
    {
        for (j = 0; j < n + 2; j++)
        {
            if (MAZE[i][j] == 0)
                color(7); // 通路为白色
            else if (MAZE[i][j] == 1)
                color(0); // 墙壁为黑色
            printf("  ");
        }
        printf("\n");
    }
    color(7);
}

MyStack *StackCreate()
{
    MyStack *stack = (MyStack *)malloc(sizeof(MyStack));
    stack->elem = (node *)malloc(sizeof(node) * M * N);
    stack->size = M * N;
    stack->top = -1;
    return stack;
}

MyQueue *QueueCreate()
{
    MyQueue *queue = (MyQueue *)malloc(sizeof(MyQueue));
    queue->node = (node *)malloc(sizeof(node) * M * N);
    queue->rear = queue->front = -1;
    return queue;
}

void PushStack(MyStack *stack, int x, int y, int pre)
{
    if (stack->top < stack->size - 1)
    {
        stack->top++;
        stack->elem[stack->top].x = x;
        stack->elem[stack->top].y = y;
        stack->elem[stack->top].pre = pre;
    }
}

void PopStack(MyStack *stack)
{
    if (stack->top >= 0)
        stack->top--;
}

int StackEmpty(MyStack *stack)
{
    return stack->top == -1 ? 1 : 0;
}

node GetStackTop(MyStack *stack)
{
    if (stack->top >= 0)
        return stack->elem[stack->top];
}

void PushQueue(MyQueue *queue, int x, int y, int pre)
{
    if (queue->rear < M

{
        if (queue->rear < M * N - 1)
        {
            queue->rear++;
            queue->node[queue->rear].x = x;
            queue->node[queue->rear].y = y;
            queue->node[queue->rear].pre = pre;
        }
}

void PopQueue(MyQueue *queue)
{
    if (queue->front < queue->rear)
        queue->front++;
}

int QueueEmpty(MyQueue *queue)
{
    return queue->front == queue->rear ? 1 : 0;
}

node GetQueueFront(MyQueue *queue)
{
    if (queue->front < queue->rear)
        return queue->node[queue->front + 1];
}

void FindPath(MyQueue *queue, MyStack *stack, int sx, int sy, int MAZE[][N], int MARK[][N], int m, int n)
{
    PushQueue(queue, sx, sy, -1);
    MARK[sx][sy] = 1;

    while (!QueueEmpty(queue))
    {
        node front = GetQueueFront(queue);
        PopQueue(queue);

        int x = front.x;
        int y = front.y;
        int pre = front.pre;

        if (x == 1 && y == 1)
        {
            PushStack(stack, x, y, pre);
            break;
        }

        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (nx >= 1 && nx <= m && ny >= 1 && ny <= n && MAZE[nx][ny] == 0 && MARK[nx][ny] == 0)
            {
                PushStack(stack, x, y, pre);
                PushQueue(queue, nx, ny, stack->top);
                MARK[nx][ny] = 1;
            }
        }
    }
}
void PrintPath(MyStack *stack, int MAZE[][N])
{
    int m, n;
    printf("请输入迷宫的行数和列数：\n");
    scanf("%d %d", &m, &n);

    printf("路径如下：\n");
    while (!StackEmpty(stack))
    {
        node top = GetStackTop(stack);
        PopStack(stack);
        int x = top.x;
        int y = top.y;
        MAZE[x][y] = 2;
    }

    OutPutMaze(MAZE, m, n);
    printf("路径的长度为：%d\n", stack->top + 2);
}

```