问题 1742 --算法3-3:迷宫

1742: 算法3-3:迷宫

时间限制: 1 Sec  内存限制: 32 MB
提交: 179  解决: 92
[提交][状态][讨论版][数据上传:][下载FPS1元][下载测试数据1元][20kb]

题目描述

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

输入

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

输出

机器人走过的路径状态。

样例输入

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

样例输出

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

提示

提示:


位置,元素以及迷宫的类型定义:

typedef struct{

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

}PosType;

 

typedef struct{

    int ord;       // 通道块在路径上的序号

    PosType seat; // 通道块在迷宫中的“坐标位置”

    int di;            // 从此通道块走向下一通道块的“方向”

}SElemType;           // 定义堆栈元素的类型

 

typedef struct{

    char arr[10][11];

}MazeType; // 定义迷宫类型(二维字符数组)


总结:

可以试着自己写个dfs(深度优先搜索)。

来源

[提交][状态]