Dungeon Master II#1472
Generally, a brute force method produces only two kinds of replies:
a. Accepted b. Time Limit Exceeded
You are probably familiar with Dungeon Master! You are trapped in a 4 \times 4 two-dimensional dungeon and must find the quickest way out. The dungeon consists of unit cells, each of which may be empty or filled with rock. It takes one minute to move to an adjacent cell to the north, south, east, or west (diagonal moves are not allowed). The dungeon is surrounded by solid, impassable rock. You also have the ability to move a rock from a neighboring cell (north, south, east, or west) to another empty neighboring cell in one minute.
Is escape possible? If so, what is the minimum time needed to escape?
The input consists of several dungeons. Each dungeon is described by lines, each with characters. Each character represents a cell of the dungeon: a cell filled with rock is denoted by #, and an empty cell by .. Your starting position is marked with S, and the exit is marked with E. There is a single blank line after each level.
For each maze, output one line. If it is possible to reach the exit, print a line of the form Escaped in x minute(s)., where x is replaced by the minimum time to escape.
If escape is not possible, print Trapped!
Example 1