Estado:  Passado  Inicio:  20141004 12:30:00  Fim:  20141004 16:30:00 
The 2014 ACMICPC Caribbean National Contests (Real contest)
Problema
2957  Indiana Jones is Trapped
Criado por  Carlos Joa Fong 
Adicionado por  cjoa (20140615) 
Límiteis 
Tempo Total: 60000 MS

Tempo Caso:
4000 MS
Memória: 62 MB  Saída límite (mb): 64 MB  Tamanho:
14 KB

Lenguagens activados  
Disponivel em 
Descripção
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=EFAEA1FA696A3DDAEE2408D155E4DF1FWorld 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=EFAEA1FA696A3DDAEE2408D155E4DF1FWorld 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=EFAEA1FA696A3DDAEE2408D155E4DF1FEspecificação 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=EFAEA1FA696A3DDAEE2408D155E4DF1F# : 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=EFAEA1FA696A3DDAEE2408D155E4DF1F# : 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=EFAEA1FA696A3DDAEE2408D155E4DF1F# : 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.
Especificação de saída
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=EFAEA1FA696A3DDAEE2408D155E4DF1F# : 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.
Exemplo de entrada
3
4 5
91.t.
i25..
t#...
x..t.
3 6
.....x
i###t.
..1#..
3 6
x.#...
#.##t.
i.1#..
Exemplo de saída
35
11
TRAPPED