Shortest Path in a Grid

You are given a grid of size \(m \times n\) where each cell is represented by a character. The cell can be:

• L representing land (which is traversable),
• W representing water (which is not traversable), or
• T representing a tree (which is also not traversable).

Your task is to compute the shortest path from the top-left corner (cell (0, 0)) to the bottom-right corner (cell (m-1, n-1)) by moving in the four cardinal directions (up, down, left, right) and only stepping on cells marked with L. If it is impossible to reach the destination, output \(-1\). Note that when the grid consists of a single cell, the answer is \(0\).

Input/Output Format: The input is read from stdin and the output is written to stdout.

inputFormat

The first line contains two space-separated integers \(m\) and \(n\) — the number of rows and columns of the grid respectively. The following \(m\) lines each contain a string of length \(n\) representing the grid. Each character of the string is one of:

• L for land,
• W for water,
• T for tree.

You need to determine the shortest path from the top-left cell to the bottom-right cell moving only in four cardinal directions (up, down, left, or right), and only through cells with L.

outputFormat

Output a single integer, which is the length of the shortest path from the top-left to bottom-right cell if such a path exists, or \(-1\) if it does not exist.

4 4
LLLW
WTLW
LLLW
WLLL

6