+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- Misagh, the young adventurer, has found the map to the treasure of Kish Island. The ghost zombie pirate Tabas, the infamous evil pirate of the Persian Gulf has hidden the treasure somewhere inside the Kish Dolphins Park (KDP). KDP is made up of a number of corridors forming a maze. To protect the treasure, Tabas 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. KDP has a number of gates on the boundary from which Misagh can enter the corridors. Fortunately, there may be a pack of dynamites at some gates, so if Misagh 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, Misagh cannot exit KDP and enter again, nor can he walk in 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 dynamite, Misagh can destroy a block almost immediately, so we can ignore the time required for it as well. The problem is to find the minimum time at which Misagh can reach the treasure. He may choose any gate he wants to enter KDP. # input The input consists of multiple test cases. Each test case contains the map of KDP viewed from above. The map is a rectangular matrix of characters. Misagh 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 dynamite. The letter (A) shows that there is one dynamite in the pack, (B) shows that there are two dynamites 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 last line of the input contains two dash characters (--). The width and the height of the map are at least 3 and at most 100 characters # output For each test case, write a single line containing a number showing the minimum number of days it takes Misagh to reach the treasure, if possible. If the treasure is unreachable, write IMPOSSIBLE. # example ### sample input 1 ``` *****#********* *.1....4..$...* *..***..2.....* *..2..*****..2* *..3..******37A *****9..56....* *.....******..* ***CA********** ***** *$3** *.2** ***#* -- ``` ### sample output 1 ``` 1 IMPOSSIBLE ```

حل سؤال در بانک سؤالات