Wall Climbing

Luciu wants to travel from the start point to the end point of a map that is $H$ tall and $W$ wide.

• The map is a grid with $H$ rows and $W$ columns. Each cell is either a wall or an empty cell.

• Luciu can move one cell at a time to an adjacent cell in one of the four directions: up, down, left, right. He cannot move onto a wall.

• Moving one cell takes Luciu 1 second.

• However, when Luciu climbs along a wall, he can move to an adjacent cell in one of the four directions in an instant (in 0 seconds).

  • An empty cell is called a cell adjacent to a wall if one of the cells directly above, below, left, or right of it is a wall.
  • Moving from a cell adjacent to a wall to another cell adjacent to a wall is called climbing along a wall.

Find the minimum time it takes Luciu to travel from the start point to the end point of the map.

The first line gives $H$ and $W$, separated by a space. The map is a grid with $H$ rows and $W$ columns.

From the second line, $H$ lines follow, each giving $W$ characters that describe the map.

• # denotes a wall.
• . denotes an empty cell.
• S denotes the start point of the map. The start point is an empty cell.
• E denotes the end point of the map. The end point is an empty cell.

Print the minimum time it takes Luciu to travel from the start point to the end point of the map.

• $1 \le H \le 500$
• $1 \le W \le 500$
• Every cell of the grid is given as one of the characters ., #, S, E.
• Exactly one start point S and exactly one end point E are given.
• All cells on the outermost border of the map (column 1, column $W$, row 1, row $H$) are walls.
• The case where the end point is unreachable from the start point is not given.