#394. 迷宫之最少花费时间
迷宫之最少花费时间
题目描述
小明身处一个由 行、 列格子组成的迷宫中,每分钟可以向上、下、左、右四个方向移动到一个相邻格子。迷宫中既有可以通行的空地,也有不能通过的墙,还有怪兽。
- 每次移动到空地需要 1 分钟。
- 如果移动到有怪兽的格子,需要 1 分钟的移动时间,并额外花费该格子数字所表示的时间消灭怪兽,才能继续前进。例如进入数字
3的格子总共花费 4 分钟。 - 不允许进入墙,也不能走出迷宫。
求小明从起点 Z 到出口 W 的最少总时间。站在起点时不需要花费时间,进入出口格子需要 1 分钟。
输入格式
第一行包含两个整数 ,表示迷宫的行数和列数。
接下来 行,每行恰好 个字符,表示迷宫地图:
#:墙或障碍物,不可通行;.:空地;1~9:怪兽格子,数字表示消灭怪兽额外需要的分钟数;Z:小明的起始位置;W:迷宫的出口。
保证起点 Z 和出口 W 均恰好出现一次。
输出格式
如果能够到达出口,输出一个整数,表示最短花费时间(分钟)。如果无法到达出口,输出 IMPOSSIBLE(全部大写)。
数据范围
- ;
- 起点和终点唯一且为不同格子;
- 迷宫中的字符仅为
#、.、1~9、Z和W。
样例 1
3 4
.Z..
.234
#.W.
5
样例 2
4 4
Z.1.
.32.
##4.
W#..
IMPOSSIBLE
说明
这道题可以采用深度优先搜索(DFS)+ 回溯来枚举从起点到终点的路径,记录最少耗时,并在当前耗时不小于已知答案时提前剪枝。注意在回溯时恢复访问标记。