A1685. 迷宫之最少花费时间
编程题
普及-
知识点
题目描述
小明身处在一个迷宫中，小明每分钟可以走到上下左右四个方向的相邻格之一。迷宫中有一些墙和障碍物。
小明可以走到空地上，需要花费 $1$ 分钟；也可以走到有怪兽的格子上，需要花费 $1$ 分钟，还要额外花费时间消灭怪兽才可以离开此方格。
现在小明想知道走出迷宫需要花费的最少时间。
小明可以走到空地上，需要花费 $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