本文共 13146 字，大约阅读时间需要 43 分钟。

前言

要做还原练习，手头的Demo有BUG, 想找个小程序来练习.

UI

整理后的代码

和原始程序一样，都写在一个cpp里面了.

/// @file \maze\maze.cpp#include "StdAfx.h"#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #define MAZE_ROW 10#define MAZE_COL 10#define POS_BEGIN_X 1#define POS_BEGIN_Y 1// 迷宫地图数据// map 2BYTE g_ucAryMaze[MAZE_ROW][MAZE_COL] ={    1, 1, 1, 1, 1, 1, 1, 1, 1, 1,    1, 0, 1, 0, 1, 1, 1, 1, 1, 1,    1, 0, 0, 0, 1, 1, 1, 1, 1, 1,    1, 0, 1, 0, 1, 1, 1, 1, 1, 1,    0, 0, 1, 0, 0, 0, 1, 1, 1, 1,    1, 0, 0, 0, 1, 0, 1, 1, 1, 1,    1, 1, 0, 1, 1, 0, 0, 1, 1, 1,    1, 1, 0, 1, 1, 1, 0, 0, 1, 1,    1, 0, 0, 1, 1, 1, 1, 0, 0, 1,    1, 1, 1, 1, 1, 1, 1, 1, 1, 1,};/*// map 1BYTE g_ucAryMaze[MAZE_ROW][MAZE_COL] ={    1, 1, 1, 1, 1, 1, 1, 1, 1, 1,    1, 0, 1, 0, 1, 1, 1, 1, 1, 1,    1, 0, 0, 0, 1, 1, 1, 1, 1, 1,    1, 0, 1, 0, 1, 1, 1, 1, 1, 1,    1, 0, 1, 0, 0, 0, 1, 1, 1, 1,    1, 0, 0, 0, 1, 0, 1, 1, 1, 1,    1, 1, 0, 1, 1, 0, 0, 1, 1, 1,    1, 1, 0, 1, 1, 1, 0, 0, 1, 1,    1, 0, 0, 1, 1, 1, 1, 0, 0, 1,    1, 0, 1, 1, 1, 1, 1, 1, 1, 1,};*//*// map 0BYTE g_ucAryMaze[MAZE_ROW][MAZE_COL] ={    1, 1, 1, 1, 1, 1, 1, 1, 1, 1,    1, 0, 1, 0, 1, 1, 1, 1, 1, 1,    1, 0, 0, 0, 1, 1, 1, 1, 1, 1,    1, 0, 1, 0, 1, 1, 1, 1, 1, 1,    1, 0, 1, 0, 0, 0, 1, 1, 1, 1,    1, 0, 0, 0, 1, 0, 1, 1, 1, 1,    1, 1, 0, 1, 1, 0, 0, 1, 1, 1,    1, 1, 0, 1, 1, 1, 0, 0, 1, 1,    1, 1, 1, 1, 1, 1, 1, 0, 0, 0,    1, 1, 1, 1, 1, 1, 1, 1, 1, 1,};*/BYTE * g_pucAryMaze = &g_ucAryMaze[0][0];#define WALL (BYTE)1#define SPACE (BYTE)0#define PATH (BYTE)-1#define PATH_TO_PREV (BYTE)-2#define DIR_UP 3#define DIR_DOWN 1#define DIR_LEFT 4#define DIR_RIGHT 2#define DIR_WIN 0#define STR_SPACE " " // 可通过区域#define STR_PATH "." // 当前的路#define STR_PATH_TO_PREV " " // 走过的路#define STR_WALL "#" // 迷宫里面的墙#define STR_WALL_OUTSIDE_ROW "+" // 迷宫外墙-上下墙#define STR_WALL_OUTSIDE_COL "|" // 迷宫外墙-左右墙#define STR_UNKNOWN "?" // 未知// 移动方向的显示字符串#define TIP_DIR_UP "↑" // 上#define TIP_DIR_DOWN "↓" // 下#define TIP_DIR_LEFT "←" // 左#define TIP_DIR_RIGHT "→" // 右#define TIP_DIR_WIN "!" // 成功#define TIP_DIR_UNKNOWN "?" // 未知#define DISP_DELAY_MSTIME 800 // 显示延时#define ONE_ROW_DISP_CNT 8 // 1行显示8个单步信息class CNode       //定义描述迷宫中当前位置的结构类型{public:    CNode()    {        m_iRowIndex = 0;        m_iColIndex = 0;        m_iDir = 0;    }    void SetValue(int iRowIndex, int iColIndex, int iDir = 0)    {        this->m_iRowIndex = iRowIndex;        this->m_iColIndex = iColIndex;        this->m_iDir = iDir;    }    operator= (CNode Src)    {        SetValue(Src.GetRowIndex(), Src.GetColIndex(), Src.GetDir());    }    int GetRowIndex()    {        return m_iRowIndex;    }    int GetColIndex()    {        return m_iColIndex;    }    void SetDir(int iDir)    {        m_iDir = iDir;    }    int GetDir()    {        return m_iDir;    }    BOOL IsSamePos(CNode & Dst) const    {        return ((m_iRowIndex == Dst.m_iRowIndex) && (m_iColIndex == Dst.m_iColIndex));    }private:    int m_iRowIndex;    int m_iColIndex;    int m_iDir; //0:无效,1:东,2:南,3:西,4:北};class LinkNode      //链表结点{public:    LinkNode()    {        m_pNext = NULL;    }    CNode GetData()    {        return m_Data;    }    void SetData(CNode Data)    {        m_Data = Data;    }    void SetNode(LinkNode * p)    {        m_pNext = p;    }    LinkNode * GetNode()    {        return m_pNext;    }private:    CNode m_Data;    LinkNode * m_pNext;};class Stack{public:    Stack()    {        m_pTopNode = NULL;    }    ~Stack()    {        while(!IsEmpty())        {            pop();        }    }    void push(CNode e)    {        LinkNode * p = NULL;        p = new LinkNode;        p->SetData(e);        p->SetNode(m_pTopNode);        m_pTopNode = p;    }    CNode pop()    {        CNode Temp;        LinkNode * p = NULL;        if(IsEmpty())        {            _ASSERT(0);        }        else        {            p = m_pTopNode;            m_pTopNode = m_pTopNode->GetNode();            Temp = p->GetData();            delete p;            p = NULL;        }        return Temp;    }    CNode GetData()    {        _ASSERT(NULL != m_pTopNode);        return m_pTopNode->GetData();    }    LinkNode * GetFristNode()    {        return (NULL != m_pTopNode) ? m_pTopNode : NULL;    }    bool IsEmpty()    {        return (NULL == m_pTopNode) ? true : false;    }private:    LinkNode * m_pTopNode;        //指向第一个结点的栈顶指针};void SetMazeValue(BYTE * pMaze, int iRowIndex, int iColIndex, BYTE ucValue){    *(pMaze + MAZE_ROW * iRowIndex + iColIndex) = ucValue;}BYTE GetMazeValue(BYTE * pMaze, int iRowIndex, int iColIndex){    return *(pMaze + MAZE_ROW * iRowIndex + iColIndex);}BOOL IsPosOutsideMaze(int iRowIndex, int iColIndex, BOOL& bTopBottomWall, BOOL& bLeftRightWall){    BOOL bRc = FALSE;    bRc = ((0 == iRowIndex)            || ((MAZE_ROW - 1) == iRowIndex)            || (0 == iColIndex)            || ((MAZE_COL - 1) == iColIndex));    if (bRc) {        bTopBottomWall = ((0 == iRowIndex) || ((MAZE_ROW - 1) == iRowIndex));        bLeftRightWall = ((0 == iColIndex) || ((MAZE_COL - 1) == iColIndex));    }    return bRc;}// 从当前位置开始，下一步可以移动的的4个方向class COffset{public:    COffset()    {        m_iOffsetRow = 0;        m_iOffsetCol = 0;    }    COffset(int iOffsetRow, int iOffsetCol)    {        m_iOffsetRow = iOffsetRow;        m_iOffsetCol = iOffsetCol;    }    int GetOffsetRow()    {        return m_iOffsetRow;    }    int GetOffsetCol()    {        return m_iOffsetCol;    }private:    int m_iOffsetRow;    int m_iOffsetCol;};// 当前可通过位置的相邻位置偏移, 从0点钟开始逆时针方向找一下位置偏移COffset g_AryMoveToNextStep[4] = {COffset(-1, 0), COffset(0, -1), COffset(1, 0), COffset(0, 1)};bool SearchMazePath(BYTE * pMaze, int m, int n, int iPosBeginX, int iPosBeginY, Stack & StackPathOk);bool PrintMaze(BYTE * pMaze, int m, int n);void PrintMazePath(Stack & Dst); // 输出迷宫的路径BYTE * GetMaze(int & m, int & n); // 获取迷宫void RestoreMaze(BYTE * pMaze, int m, int n);int main(){    int m = 0;    int n = 0;    Stack StackPathOk;    LinkNode * pNode = NULL;    BYTE * pMaze = GetMaze(m, n);    PrintMaze(pMaze, m, n);    printf("press any key to auto find maze path\r\n");    _getch();    if(SearchMazePath(pMaze, m, n, POS_BEGIN_X, POS_BEGIN_Y, StackPathOk))    {        // 在地图中画出走出迷宫的线路图        RestoreMaze(pMaze, m, n);        pNode = StackPathOk.GetFristNode();        while(NULL != pNode)        {            SetMazeValue(pMaze, pNode->GetData().GetRowIndex(), pNode->GetData().GetColIndex(), PATH);            pNode = pNode->GetNode();        }        PrintMaze(pMaze, m, n);        Sleep(DISP_DELAY_MSTIME);        PrintMazePath(StackPathOk); // 输出路径    }    else    {        printf("走出迷宫的路径不存在...\n");    }    system("pause");    return 0;}BYTE * GetMaze(int & m, int & n) //返回存取迷宫的二维指针{    m = MAZE_ROW;    n = MAZE_COL;    return g_pucAryMaze;};bool PrintMaze(BYTE * pMaze, int m, int n){    BOOL bTopBottomWall = FALSE;    BOOL bLeftRightWall = FALSE;    int i = 0;    int j = 0;    const char * pcTmp = '\0';    system("cls");    for(i = 0; i < m; i++)    {        for(j = 0; j < n; j++)        {            // 要将BYTE转成int来switch, 否则判断不对            switch((int)GetMazeValue(pMaze, i, j))            {                case SPACE:                    pcTmp = STR_SPACE;                    break;                case PATH:                    pcTmp = STR_PATH;                    break;                case PATH_TO_PREV:                    pcTmp = STR_PATH_TO_PREV;                    break;                case WALL:                    if (IsPosOutsideMaze(i, j, bTopBottomWall, bLeftRightWall)) {                        if (bTopBottomWall) {                            pcTmp = STR_WALL_OUTSIDE_ROW;                        } else if (bLeftRightWall) {                            pcTmp = STR_WALL_OUTSIDE_COL;                        } else {                            _ASSERT(0);                        }                    } else {                        pcTmp = STR_WALL;                    }                    break;                default:                    pcTmp = STR_UNKNOWN;                    break;            }            printf("%s", pcTmp);        }        printf("\r\n");    }    return true;}void RestoreMaze(BYTE * pMaze, int m, int n){    int i = 0;    int j = 0;    // 将地图恢复原样    for(i = 0; i < m; i++)    {        for(j = 0; j < n; j++)        {            // 要将BYTE转成int来switch, 否则判断不对            switch((int)GetMazeValue(pMaze, i, j))            {                case SPACE:                    break;                case PATH:                    SetMazeValue(pMaze, i, j, SPACE);                    break;                case PATH_TO_PREV:                    SetMazeValue(pMaze, i, j, SPACE);                    break;                case WALL:                    break;                default:                    break;            }        }    }}bool SearchMazePath(BYTE * pMaze, int m, int n, int iPosBeginX, int iPosBeginY, Stack & StackPathOk){    Stack StackSearchTo;    CNode TTemp, TSearchTo, TPathOk;    int iRowIndex = 0;    int iColIndex = 0;    int iLoopIndex;    BOOL bTopBottomWall = FALSE;    BOOL bLeftRightWall = FALSE;    TTemp.SetValue(iPosBeginX, iPosBeginY);    if(SPACE != GetMazeValue(pMaze, iPosBeginX, iPosBeginY))    {        return false;    }    StackSearchTo.push(TTemp);    StackPathOk.push(TTemp);    SetMazeValue(pMaze, iPosBeginX, iPosBeginY, PATH);    while(!StackSearchTo.IsEmpty())    {        PrintMaze(pMaze, m, n);        Sleep(DISP_DELAY_MSTIME);        TSearchTo = StackSearchTo.GetData();        TPathOk = StackPathOk.GetData();        if(!TPathOk.IsSamePos(TSearchTo))        {            StackPathOk.push(TSearchTo);        }        for(iLoopIndex = 0; iLoopIndex < 4; iLoopIndex++)        {            // 计算下一步的位置, 当前位置的4个相邻位置中可以通过的位置            iRowIndex = TSearchTo.GetRowIndex() + g_AryMoveToNextStep[iLoopIndex].GetOffsetRow();            iColIndex = TSearchTo.GetColIndex() + g_AryMoveToNextStep[iLoopIndex].GetOffsetCol();            if(SPACE == GetMazeValue(pMaze, iRowIndex, iColIndex)) //判断新位置是否可通过            {                // 当前位置是一个可以通过的空间                TTemp.SetValue(iRowIndex, iColIndex);                SetMazeValue(pMaze, iRowIndex, iColIndex, PATH); //标志新位置已到达过                StackSearchTo.push(TTemp); //新位置入栈                // 判断这个可通过的空间, 是否已经到达了迷宫边界                if(IsPosOutsideMaze(iRowIndex, iColIndex, bTopBottomWall, bLeftRightWall))                {                    // 成功到达出口                    StackPathOk.push(TTemp); // 把最后一个位置入栈                    return true; // 表示成功找到路径                }            }        }        if(StackPathOk.GetData().IsSamePos(StackSearchTo.GetData()))        {            // 如果无路可走，返回到上一个位置            if(!StackPathOk.IsEmpty())            {                TTemp = StackPathOk.pop();                if(!StackSearchTo.IsEmpty())                {                    StackSearchTo.pop();                }                else                {                    _ASSERT(0);                }                // 不仅搜索过，而且路径达到不了迷宫出口，已经回退                SetMazeValue(pMaze, TTemp.GetRowIndex(), TTemp.GetColIndex(), PATH_TO_PREV);            }            else            {                _ASSERT(0);            }        }    }    return false;}void PrintMazePath(Stack & Dst){    Stack ToDisp; // 定义一个栈，按从入口到出口存取路径    int iOffsetX = 0;    int iOffsetY = 0;    int iPos = 0;    const char * pcTmp = NULL;    CNode Ttmp, Ttmp1;    char cTmp = '\0';    Ttmp = Dst.pop(); //取栈p的顶点元素，即第一个位置    ToDisp.push(Ttmp); //第一个位置入栈    printf("走出迷宫的路径(坐标,方向)\n");    // 行进方向    while(!Dst.IsEmpty())    {        Ttmp = Dst.pop();       //获取下一个位置        Ttmp1 = ToDisp.GetData();        // 判断行走方向        iOffsetX = Ttmp1.GetRowIndex() - Ttmp.GetRowIndex();        iOffsetY = Ttmp1.GetColIndex() - Ttmp.GetColIndex();        if(1 == iOffsetX)        {            Ttmp.SetDir(DIR_DOWN);        }        else if(1 == iOffsetY)        {            Ttmp.SetDir(DIR_RIGHT);        }        else if(-1 == iOffsetX)        {            Ttmp.SetDir(DIR_UP);        }        else if(-1 == iOffsetY)        {            Ttmp.SetDir(DIR_LEFT);        }        ToDisp.push(Ttmp);    }    // 画走出迷宫的线路图    // 打印路径数据    while(!ToDisp.IsEmpty())    {        Ttmp = ToDisp.pop();        switch(Ttmp.GetDir())        {            case DIR_DOWN:                pcTmp = TIP_DIR_DOWN;                break;            case DIR_RIGHT:                pcTmp = TIP_DIR_RIGHT;                break;            case DIR_UP:                pcTmp = TIP_DIR_UP;                break;            case DIR_LEFT:                pcTmp = TIP_DIR_LEFT;                break;            case DIR_WIN:                pcTmp = TIP_DIR_WIN;                break;            default:                pcTmp = TIP_DIR_UNKNOWN;                break;        }        // 打印坐标, 提示        printf("[%d,%d]%s ", Ttmp.GetRowIndex(), Ttmp.GetColIndex(), pcTmp);        if((0 != iPos) && (iPos % (ONE_ROW_DISP_CNT - 1) == 0))        {            iPos = 0;            printf("\r\n");        }        else        {            iPos++;        }    }    printf("\r\n");}
       
      
     
    
   

转载地址：https://lostspeed.blog.csdn.net/article/details/52551073 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！