Maximize the Minimum Distance from Trees

Vjekoslav, a lone wolf, is fleeing from a pack of ruthless hunters lurking behind trees. Although the hunters hide behind trees, Vjekoslav doesn't know which tree conceals one. To be safe, he wants to keep as far away from any tree as possible during his escape to his cozy den. The forest is abstracted as an \(N \times M\) matrix. Each cell is either empty (denoted by .) or contains a tree at its center (denoted by +). Vjekoslav's starting position is marked with a V and his den with a J. The distance between Vjekoslav and a tree is defined as the Manhattan distance between their cells, i.e., if a cell is at \((r_1, c_1)\) and a tree is at \((r_2, c_2)\), the distance is \(|r_1 - r_2| + |c_1 - c_2|\) in \(\LaTeX\) format.

Vjekoslav can move in the four cardinal directions (north, south, east, and west), and note that trees do not block his movement. Your task is to find a path from V to J such that the minimum distance to any tree encountered along the path is maximized. Remember: the path must include the cell marked with J as the den does not occupy the entire cell.

inputFormat

The first line contains two integers \(N\) and \(M\) (the number of rows and columns of the grid). The following \(N\) lines each contain a string of length \(M\), representing the grid. The characters in the grid can be:

• .: an empty cell,
• +: a cell with a tree,
• V: Vjekoslav's starting position (appears exactly once),
• J: Vjekoslav's den (appears exactly once).

outputFormat

Output a single integer representing the maximum possible value of the minimum Manhattan distance from any tree along a valid path from V to J.

sample

3 3
V..
.+.
..J

1