2957 - Indiana Jones is Trapped

Created by Carlos Joa Fong
Added by cjoa (2014-06-15)
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 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=199D9E762D36192B52A739D138201764

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=199D9E762D36192B52A739D138201764

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=199D9E762D36192B52A739D138201764

Input 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=199D9E762D36192B52A739D138201764# : 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=199D9E762D36192B52A739D138201764# : 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=199D9E762D36192B52A739D138201764# : 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=199D9E762D36192B52A739D138201764# : 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

Hint(s)