#CF2041D. 醉酒迷宫 / Drunken Maze
醉酒迷宫 / Drunken Maze
题目描述
给定一个二维迷宫,包含起点与终点。你的任务求出从起点到达终点的最少步数,一步可以向上下左右四个方向移动一格,不能穿墙。
但是有一条限制:同一个方向连续走的步数不能超过三步,如果同一个方向连续走超过三步就会失去平衡摔倒,该行为是禁止的。 例如可以向右走三步,向左走一步,再向右走三步;整体效果等价于向右走五步,但总步数会更多。
输入格式
第一行两个整数 ,代表迷宫的行数与列数。接下来给出迷宫的 ASCII 字符图:# 代表墙,. 代表空地,S 代表起点,T 代表终点。
- 字符只包含
.、#、S、T,迷宫有且仅有一个S和一个T。 - 迷宫最外圈全部是墙
#。
输出格式
输出从起点到达终点的最小步数;无法到达输出 -1。
7 12
############
#S........T#
#.########.#
#..........#
#..........#
#..#..#....#
############
15
5 8
########
#......#
#.####.#
#...T#S#
########
14
5 8
########
#.#S...#
#.####.#
#...T#.#
########
-1