Status:  Past  Start:  20141004 12:30:00  End:  20141004 16:30:00 
The 2014 ACMICPC Caribbean National Contests (Real contest)
Problem
2957  Indiana Jones is Trapped
Created by  Carlos Joa Fong 
Added by  cjoa (20140615) 
Limits 
Total Time: 60000 MS

Test Time:
4000 MS
Memory: 62 MB  Output: 64 MB  Size:
14 KB

Enabled languages  
Available in 
Description
World famous archaeologist Indiana Jones is trapped inside a RbyC rectangularshaped room: with R rows and each row has C cells. Some of the cells have pillars and are impassable. Others have special tiles that, when pressure is simultaneously applied on all of them, open the door to exit the room. Lying around in other cells, there are stones with some weight that Indiana can pick up and move to the cells with a special tile. There is no more than one stone per cell.
To move a stone onto one of the cells with a special tile, Indiana spends an amount of energy equal to w * (d + 2), where w is the weight of the stone and d is the distance traveled.
In one step, Indiana can move from cell A to cell B if cell B is not blocked (by a pillar) and both cells share an edge. The distance traveled is defined by the minimum number of steps Indiana must take to get from the origin cell to the destination cell. If he is not carrying any stone, Indiana does not spend any amount of energy to move from one cell to another.
Given the map of the room, help Indiana escape with the least effort possible, that is, the minimum amount of energy he needs to spend to escape from the room.
;jsessionid=02C344744BD1B279D1760676CC7F669DWorld famous archaeologist Indiana Jones is trapped inside a RbyC rectangularshaped room: with R rows and each row has C cells. Some of the cells have pillars and are impassable. Others have special tiles that, when pressure is simultaneously applied on all of them, open the door to exit the room. Lying around in other cells, there are stones with some weight that Indiana can pick up and move to the cells with a special tile. There is no more than one stone per cell.
To move a stone onto one of the cells with a special tile, Indiana spends an amount of energy equal to w * (d + 2), where w is the weight of the stone and d is the distance traveled.
In one step, Indiana can move from cell A to cell B if cell B is not blocked (by a pillar) and both cells share an edge. The distance traveled is defined by the minimum number of steps Indiana must take to get from the origin cell to the destination cell. If he is not carrying any stone, Indiana does not spend any amount of energy to move from one cell to another.
Given the map of the room, help Indiana escape with the least effort possible, that is, the minimum amount of energy he needs to spend to escape from the room.
;jsessionid=02C344744BD1B279D1760676CC7F669DWorld famous archaeologist Indiana Jones is trapped inside a RbyC rectangularshaped room: with R rows and each row has C cells. Some of the cells have pillars and are impassable. Others have special tiles that, when pressure is simultaneously applied on all of them, open the door to exit the room. Lying around in other cells, there are stones with some weight that Indiana can pick up and move to the cells with a special tile. There is no more than one stone per cell.
To move a stone onto one of the cells with a special tile, Indiana spends an amount of energy equal to w * (d + 2), where w is the weight of the stone and d is the distance traveled.
In one step, Indiana can move from cell A to cell B if cell B is not blocked (by a pillar) and both cells share an edge. The distance traveled is defined by the minimum number of steps Indiana must take to get from the origin cell to the destination cell. If he is not carrying any stone, Indiana does not spend any amount of energy to move from one cell to another.
Given the map of the room, help Indiana escape with the least effort possible, that is, the minimum amount of energy he needs to spend to escape from the room.
;jsessionid=02C344744BD1B279D1760676CC7F669DInput specification
First line of input contains the number of test cases T (T <= 10) to follow. Each test case starts with an empty line, followed by a line containing integer R and C (1 <= R, C <= 50), the dimensions of the room. Each of the next R lines has exactly C characters describing a room where Indiana is currently trapped in. The meaning of these characters are as follows:
 . : empty cell
 ;jsessionid=02C344744BD1B279D1760676CC7F669D# : blocked by a pillar
 t : cell with special tile
 1 .. 9 : cell with a stone of weight equal to the corresponding digit
 i : cell where Indiana is currently located at
 x : cell with a door leading to an exit
There is exactly one cell with letter 'i' and exactly one with letter 'x'. There will be at least one special tile and at most 50 stones in the room.
First line of input contains the number of test cases T (T <= 10) to follow. Each test case starts with an empty line, followed by a line containing integer R and C (1 <= R, C <= 50), the dimensions of the room. Each of the next R lines has exactly C characters describing a room where Indiana is currently trapped in. The meaning of these characters are as follows:
 . : empty cell
 ;jsessionid=02C344744BD1B279D1760676CC7F669D# : blocked by a pillar
 t : cell with special tile
 1 .. 9 : cell with a stone of weight equal to the corresponding digit
 i : cell where Indiana is currently located at
 x : cell with a door leading to an exit
There is exactly one cell with letter 'i' and exactly one with letter 'x'. There will be at least one special tile and at most 50 stones in the room.
First line of input contains the number of test cases T (T <= 10) to follow. Each test case starts with an empty line, followed by a line containing integer R and C (1 <= R, C <= 50), the dimensions of the room. Each of the next R lines has exactly C characters describing a room where Indiana is currently trapped in. The meaning of these characters are as follows:
 . : empty cell
 ;jsessionid=02C344744BD1B279D1760676CC7F669D# : blocked by a pillar
 t : cell with special tile
 1 .. 9 : cell with a stone of weight equal to the corresponding digit
 i : cell where Indiana is currently located at
 x : cell with a door leading to an exit
There is exactly one cell with letter 'i' and exactly one with letter 'x'. There will be at least one special tile and at most 50 stones in the room.
Output specification
For each test case, output a line containing the word "TRAPPED" if Indiana is not able to escape from the room. Otherwise, output a line containing the minimum amount of energy Indiana needs to escape from the room.
For each test case, output a line containing the word "TRAPPED" if Indiana is not able to escape from the room. Otherwise, output a line containing the minimum amount of energy Indiana needs to escape from the room.
First line of input contains the number of test cases T (T <= 10) to follow. Each test case starts with an empty line, followed by a line containing integer R and C (1 <= R, C <= 50), the dimensions of the room. Each of the next R lines has exactly C characters describing a room where Indiana is currently trapped in. The meaning of these characters are as follows:
 . : empty cell
 ;jsessionid=02C344744BD1B279D1760676CC7F669D# : blocked by a pillar
 t : cell with special tile
 1 .. 9 : cell with a stone of weight equal to the corresponding digit
 i : cell where Indiana is currently located at
 x : cell with a door leading to an exit
There is exactly one cell with letter 'i' and exactly one with letter 'x'. There will be at least one special tile and at most 50 stones in the room.
Sample input
3
4 5
91.t.
i25..
t#...
x..t.
3 6
.....x
i###t.
..1#..
3 6
x.#...
#.##t.
i.1#..
Sample output
35
11
TRAPPED