Estado:  Pasado  Inicio:  20141004 12:30:00  Fin:  20141004 16:30:00 
The 2014 ACMICPC Caribbean National Contests (Real contest)
Problema
2957  Indiana Jones is Trapped
Creado por  Carlos Joa Fong 
Adicionado por  cjoa (20140615) 
Límites 
Tiempo Total: 60000 MS

Tiempo Caso:
4000 MS
Memoria: 62 MB  Salida límite (mb): 64 MB  Tamaño:
14 KB

Lenguajes activados  
Disponible en 
Descripción
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=2C74C0D2B10FE649B28B72CB9386A0BAWorld 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=2C74C0D2B10FE649B28B72CB9386A0BAWorld 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=2C74C0D2B10FE649B28B72CB9386A0BAEspecificación de entrada
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=2C74C0D2B10FE649B28B72CB9386A0BA# : 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=2C74C0D2B10FE649B28B72CB9386A0BA# : 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=2C74C0D2B10FE649B28B72CB9386A0BA# : 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.
Especificación de salida
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=2C74C0D2B10FE649B28B72CB9386A0BA# : 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.
Ejemplo de entrada
3
4 5
91.t.
i25..
t#...
x..t.
3 6
.....x
i###t.
..1#..
3 6
x.#...
#.##t.
i.1#..
Ejemplo de salida
35
11
TRAPPED