Ice Maze

Interview

Time limit1sMemory limit1024 MB

Summary

Find the least total slipperiness time for Tera to reach the exit by sliding on ice and stopping only at rocks, or report -1 if escape is impossible.

Level: Medium4 of 10
Topics: Shortest path, Graph, Matrix
Solved: No attempts yet

Problem

Explorer Tera is trapped in an ice maze. The floor of the maze is slippery ice, so once Tera steps onto it, Tera slides until hitting a rock. For example, in the picture above, if Tera moves left, Tera cannot stop midway and slides until hitting the rock on the left. The outside of the maze is a cliff, so falling off means Tera can never escape.

The ice maze contains 4 kinds of objects.

Tera: The explorer trapped in the maze. Tera can move in 4 directions: up, down, left, and right. There is exactly 1 Tera in the maze. The slipperiness time of the ice where Tera starts is 0.
Rock: Cannot be passed through. If Tera slides into a rock, Tera stops in front of it.
Hole: If Tera falls into a hole, Tera can never escape.
Exit: Entering the exit immediately escapes the ice maze. There is exactly 1 exit in the maze.

The time it takes to slide across a piece of ice is called its slipperiness time. Each piece of ice can have a different slipperiness time.

When Tera moves in one direction, the travel time is the sum of the slipperiness times of the ice pieces Tera occupies while sliding. Two rules apply to travel time:

When Tera starts moving in a direction, the slipperiness time of the starting ice is not included.
When Tera enters the exit, the slipperiness time of the exit ice is not included.

In the picture above, consider the travel time when Tera moves up. Excluding the slipperiness time 4 of the starting ice and the slipperiness time 0 of the exit ice, the time taken is 1 + 2 = 3 before Tera escapes through the exit.

Tera is suffering from hypothermia and wants to escape the ice maze as quickly as possible. Compute the shortest time needed to escape the maze.

Input

The first line contains two integers W ( $2 \le W \le 500$ ), the width of the maze, and H ( $2 \le H \le 500$ ), the height of the maze.

The next H lines describe the maze. Tera is marked T, rocks are marked R, holes are marked H, and the exit is marked E. The slipperiness time t of each piece of ice is an integer from 0 to 9.

Output

If Tera can escape the maze, print the shortest escape time.

If Tera cannot escape the maze, print -1.

Examples4

Example 1
Input
```
5 5
2E115
32411
11313
R42TH
124R6
```
Expected output
```
9
```
Example 2
Input
```
4 5
11R1
1E1R
1911
1911
1T1R
```
Expected output
```
4
```
Example 3
Input
```
3 3
111
TRE
111
```
Expected output
```
-1
```
Example 4
Input
```
5 5
TRRRR
1R11R
1RE1R
1111R
RRRRR
```
Expected output
```
9
```