Corn maze

Corn farmers in southern Ontario cut mazes into their fields in the fall, after harvest.

A rectangular field is a grid. Each cell is one of the following.

• #: standing cornstalks. Jack cannot enter this cell.
• X: an obstacle such as a tree or a building. Jack cannot enter this cell.
• .: a crushed pathway. Jack can enter this cell.

Exactly one crushed cell lies on the perimeter of the grid. That cell is the entrance. Every other crushed cell is in the interior.

Jack moves between crushed cells that share an edge. He does not move diagonally.

The core is a crushed cell whose shortest path from the entrance is as long as possible. Path length is the number of crushed cells on the path, including the entrance and the core. If several cells share that maximum length, the length itself is unique.

Find the length of the shortest path from the entrance to the core.

The following grid is a finished maze. The entrance is the only pathway cell in the first row.

#.X#######
#.#X#...##
#...X#.X.#
#.#......#
#.XXXX##.#
##########

Marking the entrance as E, one core as C, and the rest of that path as + gives the grid below. The path length is 12.

#EX#######
#+#X#C+.##
#+++X#+X.#
#.#++++..#
#.XXXX##.#
##########

The first line contains two integers $N$ and $M$, the number of rows and the number of columns.

Each of the next $N$ lines contains a string of $M$ characters. Each character is #, X, or ..

Exactly one . lies on the perimeter. Every . is reachable from the entrance.

Print a single integer: the length of the shortest path from the entrance to the core.

• $1 \le N, M \le 200$
• Each cell is #, X, or ..
• Exactly one . lies on the perimeter.
• Every . is reachable from the entrance.