. 【提高】小H回家
【提高】小H回家
You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.
说明
小H在一个划分成了n*m个方格的长方形封锁线上。 每次他能向上下左右四个方向移动一格(当然小H不可以静止不动), 但不能离开封锁线,否则就被打死了。 刚开始时他有满血6点,每移动一格他要消耗1点血量。一旦小H的 血量降到 0, 他将死去。 他可以沿路通过拾取金币来补满血量。只要他走到有金币的格子,他不需要任何时间即可拾取。格子上的金币可以瞬间补满,所以每次经过这个格子都有金币。就算到了某个有金币的格子才死去, 他也不能通过拾取金币补满血。 即使在家门口死去, 他也不能算完成任务回到家中。
地图上有 5 种格子:
数字 0: 障碍物。数字 1: 空地, 小H可以自由行走。
数字 2: 小H出发点, 也是一片空地。
数字 3: 小H的家。
数字 4: 有金币在上面的空地。
小H能否安全回家?如果能, 最短需要多长时间呢?
输入格式
第一行两个整数n,m, 表示地图的大小为n*m。
下面 n 行, 每行 m 个数字来描述地图。
(1<=n,m<=9)
输出格式
一行, 若小H不能回家, 输出-1,否则输出他回家所需最短时间。
样例
3 3
2 1 1
1 1 0
1 1 3
4
第七届SWPU-ACM老生预选赛
- Status
- Done
- Rule
- ACM/ICPC
- Problem
- 187
- Start at
- 2022-9-19 14:00
- End at
- 2022-10-28 14:00
- Duration
- 936 hour(s)
- Host
- Partic.
- 45