← 返回题单
题单练习 深度优先搜索
← 上一题 下一题 →

A1685 | 迷宫之最少花费时间

时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

小明身处在一个迷宫中，小明每分钟可以走到上下左右四个方向的相邻格之一。迷宫中有一些墙和障碍物。

小明可以走到空地上，需要花费 $1$ 分钟；也可以走到有怪兽的格子上，需要花费 $1$ 分钟，还要额外花费时间消灭怪兽才可以离开此方格。

现在小明想知道走出迷宫需要花费的最少时间。

输入格式

第一行为两个整数 $n$ 和 $m$ ($1 = n , m = 20$)。以下 $n$ 行每行有 $m$ 个字符，即迷宫地图。

其中 # 代表墙和障碍物，. 表示空地，[1~9] 的数字代表此处有怪兽以及消灭此处的怪兽需要的时间。

Z 表示小明的起始位置，W 表示迷宫出口。

对于每组数据保证起始位置和迷宫出口唯一。

输出格式

输出走出迷宫的最短时间(单位：分钟)。如果无法走出迷宫则输出 IMPOSSIBLE 。

输入输出样例

输入 #1
3 4
.Z..
.234
#.W.
输出 #1
5
输入 #2
4 4
Z.1.
.32.
##4.
W#..
输出 #2
IMPOSSIBLE
C++ 编辑器
输入
输出