二叉搜索树在数据结构方面的综合运用,如何利用C语言编程解决这个算法?

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

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问

相似问题

0
多叉树的快速搜索算法的优化,这个问题如何利用C语言的办法解决
0
二叉平衡树的高效率的求法的问题,运用C语言系统的编程的技术
1
大佬们帮忙看看这个二叉搜索树哪错了
1
在查找方面二叉排序树效率与顺序查找的效率谁高(这里一般二叉排序树 不是指平衡二叉树)
0
数据结构里的AVL树的计算的问题,怎么才能利用C语言程序的过程来实现编写
0
应用在子树上的数据结构的查询的算法,利用C语言的程序设计的方式来实现?
0
翻转数据结构的树的节点,怎么利用C语言的程序的设计的形式来实现的
0
数据结构里的树的合并转移的算法,利用C语言的程序的设计的实现的方式怎么做?
0
树的数据结构的可见性的判断的算法的问题,如何利用C语言的程序的编写的过程实现计算的?
2
(C语言)在二叉搜索树的学习时遇到了问题,求大佬帮忙看看
0
关于数据结构上面的子树的查询问题,怎么运用C语言的程序设计代码的编写的思想解决呢?
0
数据结构的子树查询的问题,怎么利用C语言的程序编程的方式实现的代码的呢?
1
C语言数据结构二叉树-目录树的基本操作求解?
0
输入字符串构建两个二叉搜索树
1
数据结构java实验四验证教材中树结构的基本操作,设计实现指定操作的算法,并做算法分析。 以下各题二叉树的存储结构是二叉链表表示,方法声明如下: 二叉树的二叉链表结点类:
1
一个二叉排序树输出的问题
1
采用用户输入元素并基于前序遍历的方式创建一个存储人名的二叉链表树包含7个节点,用户输入两个人的姓名,比较这两个人的子孙谁多
3
求助二叉树一道难题,怎么进行后序遍历输入,要求C语言
0
利用普利姆算法和克鲁斯卡尔算法实现最小生成树问题C语言或者C++语言实现
1
如何用C语言编程分析高阶函数并有图像