Treasure Hunt

You are given a rectangular grid representing a forest with N rows and M columns. Each cell in the grid is either walkable ('.') or blocked ('#'). Starting from a given cell (sx, sy), your task is to determine the minimum number of steps required to reach the destination cell (ex, ey). You are only allowed to move up, down, left, or right (i.e. in the four cardinal directions). Each move counts as one step.

If there is no valid path from the start to the destination, output Trapped!.

The movement directions can be expressed in LaTeX as follows:

$$\{(dx,dy)\} = \{(-1,0),\; (1,0),\; (0,-1),\; (0,1)\}$$

inputFormat

The first line contains two integers N and M separated by a space, representing the number of rows and columns of the forest grid.

This is followed by N lines, each containing a string of length M comprised of characters . and # representing the forest.

The last line contains four integers sx sy ex ey separated by spaces, representing the row and column indices of the starting cell and the destination cell respectively. The indices are zero-based.

outputFormat

Output a single line: the minimum number of steps required to reach the destination from the start, or Trapped! if no such path exists.

5 5
.....
.###.
.....
.###.
.....
0 0 4 4

8