Dungeon Crawler

Problem Description
You are testing a new exploration robot in a grid-like dungeon. The dungeon is represented as an $R$-by-$C$ grid. The rows are numbered $1, 2, \dots, R$ and the columns are numbered $1, 2, \dots, C$.

The robot starts at the cell marked S and needs to reach the exit marked E. The robot can move up, down, left, or right to an adjacent cell in one step. It cannot move diagonally, it cannot move outside the boundaries of the dungeon, and it cannot move into a cell containing a wall, marked as #. Empty spaces are marked as ..

Since the robot's battery is limited, you need to determine the minimum number of steps required to reach the exit.

Input Specification
The first line of the input will be an integer $R$ ($1 \le R \le 1\,000$). The second line of the input will be an integer $C$ ($1 \le C \le 1\,000$). The next $R$ lines each contain a string of exactly $C$ characters representing the dungeon. There will be exactly one S and exactly one E. All other characters will be either . or #.

• For 3 of the 15 available marks, $R \le 10$ and $C \le 10$.
• For an additional 4 of the 15 available marks, there are no walls in the dungeon (all characters except S and E are .).
• For an additional 4 of the 15 available marks, $R \le 200$ and $C \le 200$.
• For the remaining 4 marks, no further constraints apply.

Output Specification
Output the minimum number of steps required for the robot to reach the exit. If it is impossible to reach the exit, output trapped.

Sample Input 1

Output for Sample Input 1

Explanation of Output for Sample Input 1

The robot can take the following path: move right, move right, move down, move down, move right. This takes a total of 5 steps. It is impossible to reach the exit in fewer steps.

Sample Input 2

Output for Sample Input 2

Explanation of Output for Sample Input 2

The robot is blocked by walls on all valid adjacent sides and cannot make any moves. Therefore, it is impossible to reach the exit.