C++迷宫(栈实现),无法回溯

Maze.c


 /*********************************
 *                               *
 * 文件夹: ▲03 栈和队列\04 Maze *
 *                               *
 * 文件名: Maze.c                *
 *                               *
 * 算  法: 3.3                   *
 *                               *
 *********************************/

#ifndef MAZE_C
#define MAZE_C

#include "Maze.h"                           //**▲03 栈和队列**//

/*════╗
║ 算法3.3║ 
╚════*/
Status MazePath(MazeType maze[][N], PosType start, PosType end)
{
    SqStack S;
    SElemType_Sq nodeInf;                   //nodeInf存储当前通道块信息 
    PosType curPos;                         //当前位置 
    int curStep;                            //当前通道块序号 

    InitStack_Sq(&S);
    curPos = start;                         //设定当前位置为"出口位置" 
    curStep = 1;

    do
    {
        if(Pass(curPos, maze))              //当前位置可通过,即是未曾访问的通道块 
        {
            FootPrint(curPos, maze);        //留下足迹:即方向设为East
            ShowMaze(maze); 

            SetSElemType(&nodeInf, curStep, curPos, East);  //设置通道块信息
            Push_Sq(&S, nodeInf);           //加入路径 

            if(EqualPosType(curPos, end))   //到达终点
            {
                printf("\n寻路成功!!\n\n");
                return TRUE;    
            }

            curPos = NextPos(curPos, East); //下一位置是当前位置的东邻 
            curStep++;                      //探索下一步 
        }
        else                                //当前位置不能通过 
        {
            if(!StackEmpty_Sq(S))
            {
                Pop_Sq(&S, &nodeInf);       //修改结点指向

                while(nodeInf.di==North && !StackEmpty_Sq(S))   //此通道块4个方向都遍历过 
                {
                    MarkPrint(nodeInf.seat, maze);              //留下不能通过的标记
                    ShowMaze(maze);

                    Pop_Sq(&S, &nodeInf);                //正常来说这里应该回溯一下
                    //GetTop_Sq(S,&nodeInf);                    //更新一下nodeInf的值
                    nodeInf = *(S.top-1);

                    curPos = nodeInf.seat;                  //目的是让当前的curPos指向刚刚出站的那个元素,要不这curPos回不去
                }

                if(nodeInf.di<North)
                {
                    maze[nodeInf.seat.x][nodeInf.seat.y] = ++nodeInf.di;//改变探索方向,在迷宫数组中留下标记   
                    ShowMaze(maze);

                    Push_Sq(&S, nodeInf);

                    curPos = NextPos(nodeInf.seat, nodeInf.di);
                }
            }
        }       
    }while(!StackEmpty_Sq(S));  

    printf("\n寻路失败!!\n\n");

    return FALSE;   
}

void InitMaze(MazeType maze[][N], PosType *start, PosType *end) 
{                                               //迷宫规模为N×N 
    int i, j, tmp;

    srand((unsigned)time(NULL));                //用系统时间做随机数种子 

    for(i=0; i<N; i++)
    {
        for(j=0; j<N; j++)
        {
            if(i==0 || j==0 || i==N-1 || j==N-1)
                maze[i][j] = Wall;              //迷宫外墙
            else
            {
                tmp = rand()%X;                 //生成随机数填充迷宫       
                if(!tmp)
                    maze[i][j] = Obstacle;      //1/X的概率生成障碍 
                else
                    maze[i][j] = Way;           //其它地方加入路径 
            }
        }   
    }

    (*start).x = 1;                             //迷宫入口
    (*start).y = 0;
    (*end).x = N-2;                             //迷宫出口 
    (*end).y = N-1; 

    maze[1][0] = maze[N-2][N-1] = Way;          //开放入口和出口 
    maze[1][1] = maze[N-2][N-2] = Way;          //为了提高成功率,入口处和出口处临近的结点一直设为通路 
}

void PaintMaze(MazeType maze[][N])
{
    int i, j;

    for(i=0; i<N; i++)
        for(j=0; j<N; j++)
        {
            if(maze[i][j]==Wall)                //外墙 
                printf("▇");
            else if(maze[i][j]==Obstacle)       //内部障碍 
                printf("▓");
            else if(maze[i][j]==East)           //朝东探索
                printf("→");
            else if(maze[i][j]==South)          //朝南探索
                printf("↓");
            else if(maze[i][j]==West)           //朝西探索
                printf("←");
            else if(maze[i][j]==North)          //朝北探索
                printf("↑");
            else if(maze[i][j]==DeadLock)       //访问过且不能通过的结点 
                printf("★");
            else                                //未访问过的路径结点 
                printf("  ");

            if(j!=0 && j%(N-1)==0)              //每隔N个结点换行 
                printf("\n");
        }
}

void ShowMaze(MazeType maze[][N])   //相当于刷新操作 
{
    Wait(SleepTime);                //暂停 
    system("cls");                  //先清除屏幕现有内容 
    PaintMaze(maze);                //在屏幕上画出迷宫 
} 

Status EqualPosType(PosType seat1, PosType seat2)
{
    if(seat1.x==seat2.x && seat1.y==seat2.y)
        return TRUE;    //两通道块坐标相等返回1 
    else
        return ERROR;
}

Status Pass(PosType seat, MazeType maze[][N])        
{
    int x = seat.x;
    int y = seat.y;

    if(!IsCross(seat) && maze[x][y]==Way)   //结点不能越界
        return TRUE;
    else
        return ERROR;
}

void FootPrint(PosType seat, MazeType maze[][N])    //所谓留下足迹即设置其下一次访问方向 
{   
    maze[seat.x][seat.y] = East;                    //初始设置向东探索 
} 

void SetSElemType (SElemType_Sq *e, int ord, PosType seat, int di)
{
    (*e).ord = ord;
    (*e).seat = seat;
    (*e).di = di;
}

PosType NextPos(PosType seat, int di)
{   
    PosType tmp = seat;

    switch(di)
    {
        case East:  tmp.y++;            //向东 
            break;  
        case South: tmp.x++;            //向南
            break;
        case West:  tmp.y--;            //向西 
            break;
        case North: tmp.x--;            //向北
            break;
    }

    return tmp;
}

Status IsCross(PosType seat)
{
    int x = seat.x;
    int y = seat.y;

    if(x<0 || y<0 || x>N-1 || y>N-1)
        return TRUE;                    //越界 
    else
        return FALSE; 
}

void MarkPrint(PosType seat, MazeType maze[][N])
{
    int x = seat.x;
    int y = seat.y;

    maze[x][y] = DeadLock;              //留下不能通过的标记 
}

#endif

maze-main.c

 /*********************************
 *                               *
 * 文件夹: ▲03 栈和队列\04 Maze *
 *                               *
 * 内  容: 迷宫相关函数测试      *
 *                               *
 *********************************/

#include "Maze.h"                       //**▲03 栈和队列**//                  

int main(int argc, char *argv[])
{
    MazeType maze[N][N];
    PosType start, end;
    SElemType_Sq e;
    char Re = 'Y';

    while(Re=='Y' || Re=='y')
    { 
        InitMaze(maze, &start, &end);   //初始化迷宫,包括出入口 
        ShowMaze(maze);                 //显示迷宫的初始状态 
        MazePath(maze,start,end);       //迷宫寻路

        printf("重置?(Y/N):");
        scanf("%c", &Re);
    }

    return 0;
}

主要问题应该出在这个循环里:

 while(nodeInf.di==North && !StackEmpty_Sq(S))  //此通道块4个方向都遍历过 
                {
                    MarkPrint(nodeInf.seat, maze);              //留下不能通过的标记
                    ShowMaze(maze);

                    Pop_Sq(&S, &nodeInf);                  //正常来说这里应该回溯一下
                }

就是说,代码没有及时更新nodeInf为栈顶元素。我想用下面这个函数处理

GetTop_Sq(S,&nodeInf); //更新一下nodeInf的值
函数定义如下:

 Status GetTop_Sq(SqStack S, SElemType_Sq *e)
{
    if(S.top==S.base)
        return ERROR;

    *e = *(S.top - 1);                          //并不破坏栈 

    return OK;
} 

但是根本不好使,第一个死胡同变成小星星就不回溯了。但是我和原作者的代码一模一样,不知道到底问题出在哪里。
图片无法上传,大家可以看下原作者的效果,连接如下:

https://www.cnblogs.com/kangjianwei101/p/5225706.html

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问