Envíos

2957 - Indiana Jones is Trapped

Criado por Carlos Joa Fong
Adicionado por cjoa (2014-06-15)
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 R-by-C rectangular-shaped 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=EFAEA1FA696A3DDAEE2408D155E4DF1F

World famous archaeologist Indiana Jones is trapped inside a R-by-C rectangular-shaped 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=EFAEA1FA696A3DDAEE2408D155E4DF1F

World famous archaeologist Indiana Jones is trapped inside a R-by-C rectangular-shaped 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=EFAEA1FA696A3DDAEE2408D155E4DF1F

Especificaçã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

Sugestões(s)