33OJ
登录 注册

#CF2041D. 醉酒迷宫 / Drunken Maze

醉酒迷宫 / Drunken Maze

题目描述

给定一个二维迷宫,包含起点与终点。你的任务求出从起点到达终点的最少步数,一步可以向上下左右四个方向移动一格,不能穿墙。

但是有一条限制:同一个方向连续走的步数不能超过三步,如果同一个方向连续走超过三步就会失去平衡摔倒,该行为是禁止的。 例如可以向右走三步,向左走一步,再向右走三步;整体效果等价于向右走五步,但总步数会更多。

输入格式

第一行两个整数 n,mn,m,代表迷宫的行数与列数。接下来给出迷宫的 ASCII 字符图:# 代表墙,. 代表空地,S 代表起点,T 代表终点。

  • 12≤n×m≤20000012 \le n\times m \le 200000
  • 3≤n,m≤100003\le n,m \le 10000
  • 字符只包含 .、#、S、T,迷宫有且仅有一个 S 和一个 T。
  • 迷宫最外圈全部是墙 #。

输出格式

输出从起点到达终点的最小步数;无法到达输出 -1。

7 12
############
#S........T#
#.########.#
#..........#
#..........#
#..#..#....#
############
15
5 8
########
#......#
#.####.#
#...T#S#
########
14
5 8
########
#.#S...#
#.####.#
#...T#.#
########
-1

原题链接

原题链接