走迷宫（数据结构，栈的应用）

【问题描述】

有一个 10 x 10 的迷宫，起点是‘S’，终点是‘E’，墙是‘#’，道路是空格。一个机器人从起点走到终点。当机器人走到一个通道块，前面已经没有路可走时，它会转向到当前面向的右手方向继续走。如果机器人能够过，则留下足迹‘*’，如果走不通，则留下标记‘!’。
下面给出算法，请你模拟机器人的走法输出最终的状态。

【输入形式】

一个 10 x 10 的二维字符数组。

【输出形式】

机器人走过的路径状态。

【样例输入】

##########
#S #   # #
#  #   # #
#    ##  #
# ###    #
#   #    #
# #   #  #
# ### ## #
##      E#
##########

【样例输出】

##########
#**#!!!# #
# *#!!!# #
#**!!##  #
#*###    #
#***#    #
# #***#  #
# ###*## #
##   ****#
##########

从起点开始按照右下左上判断是否有‘   ’，如果有则移动过去，并将点的坐标压入栈中，当无‘  ’时说明是死路，将此点标为‘ ! ’，将此点从栈中压出，并取栈顶元素，回到上一个点，重新判断不为死路的方向，由于对刚刚的方向标记了‘ ！’,所以不会再回到死路，如此循环，直到遇到终点。

#include
#include

using namespace std;

//移动方向变量
int mx[5]={0,1,0,-1};
int my[5]={1,0,-1,0};

typedef struct{
    int r, c;      // 以行号和列号作为“坐标位置”类型
}PosType;

typedef struct{
    char arr[10][11];
}MazeType; // 定义迷宫类型（二维字符数组）

void PrintMap(MazeType &map1,PosType &start1,PosType &end1)//绘制地图
{
    char temp;
    for(int i=0;i<10;i++)
        for(int j=0;j<10;j++)
        {
            temp = cin.get();
            if(temp != 'n')
                map1.arr[i][j] = temp;
            else
                j--;
            if(map1.arr[i][j] == 'S')//记录起点
            {
                start1.r = i;
                start1.c = j;
            }
            if(map1.arr[i][j] == 'E')//记录终点
            {
                end1.r = i;
                end1.c = j;
            }
        }
}

void GetMap(MazeType &map1)//打印地图
{
    for(int i=0;i<10;i++)
    {
        for(int j=0;j<10;j++)
            cout< way;//储存走过的路径
    PosType mp;//储存在移动点的坐标
    map1.arr[start1.r][start1.c] = '*';
    mp.r = start1.r;     mp.c = start1.c;//初始化动点坐标
    while(1)
    {
        s1:for(int i=0;i<4;++i)
        {
            int xx=mp.r+mx[i];
            int yy=mp.c+my[i];
            if((map1.arr[xx][yy]=='E' && xx>=0 && xx<10 && yy>=0 && yy<10))//判断是否到达终点
            {
                map1.arr[xx][yy] = '*';
                return;
            }
            if((map1.arr[xx][yy]==' ' && xx>=0 && xx<10 && yy>=0 && yy<10))//判断是否仍有未走过的路径
            {
                map1.arr[xx][yy] = '*';
                mp.r=xx;mp.c=yy;
                way.push(mp);
                goto s1;
            }
            if(i == 3)//如果没有可走路径
            {
                map1.arr[mp.r][mp.c] = '!';//标记死路
                //退回到上一个点
                way.pop();
                mp.r = way.top().r;
                mp.c = way.top().c;
                //重新判断上一个点是否还有其他选择
                goto s1;
            }
        }
    }
}
int main()
{
    MazeType map1;
    PosType start1,end1;
    PrintMap(map1,start1,end1);
    HazePath(map1,start1,end1);
    GetMap(map1);
}