编程介的小学生 2017-07-14 12:20 采纳率: 20.3%
浏览 750
已采纳

Treasure of the Chimp Island

Problem Description
Bob Bennett, the young adventurer, has found the map to the treasure of the Chimp Island, where the ghost zombie pirate LeChimp, the infamous evil pirate of the Caribbeans has hidden somewhere inside the Zimbu Memorial Monument (ZM2). ZM2 is made up of a number of corridors forming a maze. To protect the treasure, LeChimp has placed a number of stone blocks inside the corridors to block the way to the treasure. The map shows the hardness of each stone block which determines how long it takes to destroy the block. ZM2 has a number of gates on the boundary from which Bob can enter the corridors. Fortunately, there may be a pack of dynamites at some gates, so that if Bob enters from such a gate, he may take the pack with him. Each pack has a number of dynamites that can be used to destroy the stone blocks in a much shorter time. Once entered, Bob cannot exit ZM2 and enter again, nor can he walk on the area of other gates (so, he cannot pick more than one pack of dynamites).

The hardness of the stone blocks is an integer between 1 and 9, showing the number of days required to destroy the block. We neglect the time required to travel inside the corridors. Using a dynamite, Bob can destroy a block almost immediately, so we can ignore the time required for it too. The problem is to find the minimum time at which Bob can reach the treasure. He may choose any gate he wants to enter ZM2.

Input
The input consists of multiple test cases. Each test case contains the map of ZM2 viewed from the above. The map is a rectangular matrix of characters. Bob can move in four directions up, down, left, and right, but cannot move diagonally. He cannot enter a location shown by asterisk characters (*), even using all his dynamites! The character ($) shows the location of the treasure. A digit character (between 1 and 9) shows a stone block of hardness equal to the value of the digit. A hash sign (#) which can appear only on the boundary of the map indicates a gate without a dynamite pack. An uppercase letter on the boundary shows a gate with a pack of dynamites. The letter A shows there is one dynamite in the pack, B shows there are two dynamite in the pack and so on. All other characters on the boundary of the map are asterisks. Corridors are indicated by dots (.). There is a blank line after each test case. The width and the height of the map are at least 3 and at most 100 characters. The last line of the input contains two dash characters (--).

Output
For each test case, write a single line containing a number showing the minimum number of days it takes Bob to reach the treasure, if possible. If the treasure is unreachable, write IMPOSSIBLE.

Sample Input
*****#*********
.1....4..$...
..**..2.....*
..2..****..2*
..3..*****37A
*****9..56....*
.....*****..*
CA*******


$3*
.2*
***#*

Sample Output
1
IMPOSSIBLE

  • 写回答

1条回答 默认 最新

  • devmiao 2017-07-29 13:55
    关注
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

悬赏问题

  • ¥100 python读取速度问题
  • ¥15 stm32f407使用DMA问题
  • ¥15 您好 这个API接口该怎么弄 网站搭建好了 API也有 现在就不知道该怎么填写API 不知道怎么用
  • ¥88 用uniapp写一个多端的程序,用到高德地图,用高德的JSAPI吗?
  • ¥20 关于#c++#的问题:水果店管理系统
  • ¥30 dbLinq最新版linq sqlite
  • ¥20 对D盘进行分盘之前没有将visual studio2022卸载掉,现在该如何下载回来
  • ¥15 完成虚拟机环境配置,还有安装kettle
  • ¥15 2024年全国大学生数据分析大赛A题:直播带货与电商产品的大数据分析 问题5. 请设计一份优惠券的投放策略,需要考虑优惠券的数量、优惠券的金额、投放时间段和投放商品种类等因素。求具体的python代码
  • ¥15 有人会搭建生鲜配送自营+平台的管理系统吗