#394. 迷宫之最少花费时间

    ID: 394 传统题 2000ms 128MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>搜索图结构最短路深度优先搜索回溯剪枝CF信奥C++4.1-AC课程

迷宫之最少花费时间

题目描述

小明身处一个由 RR 行、CC 列格子组成的迷宫中,每分钟可以向上、下、左、右四个方向移动到一个相邻格子。迷宫中既有可以通行的空地,也有不能通过的墙,还有怪兽。

  • 每次移动到空地需要 1 分钟。
  • 如果移动到有怪兽的格子,需要 1 分钟的移动时间,并额外花费该格子数字所表示的时间消灭怪兽,才能继续前进。例如进入数字 3 的格子总共花费 4 分钟。
  • 不允许进入墙,也不能走出迷宫。

求小明从起点 Z 到出口 W 的最少总时间。站在起点时不需要花费时间,进入出口格子需要 1 分钟。

输入格式

第一行包含两个整数 R,CR,C,表示迷宫的行数和列数。

接下来 RR 行,每行恰好 CC 个字符,表示迷宫地图:

  • #:墙或障碍物,不可通行;
  • .:空地;
  • 1~9:怪兽格子,数字表示消灭怪兽额外需要的分钟数;
  • Z:小明的起始位置;
  • W:迷宫的出口。

保证起点 Z 和出口 W 均恰好出现一次。

输出格式

如果能够到达出口,输出一个整数,表示最短花费时间(分钟)。如果无法到达出口,输出 IMPOSSIBLE(全部大写)。

数据范围

  • 1≤R,C≤201\le R,C\le20;
  • 起点和终点唯一且为不同格子;
  • 迷宫中的字符仅为 #、.、1~9、Z 和 W。

样例 1

3 4
.Z..
.234
#.W.
5

样例 2

4 4
Z.1.
.32.
##4.
W#..
IMPOSSIBLE

说明

这道题可以采用深度优先搜索(DFS)+ 回溯来枚举从起点到终点的路径,记录最少耗时,并在当前耗时不小于已知答案时提前剪枝。注意在回溯时恢复访问标记。