P7775 [COCI 2009/2010 #2] VUK

This problem is from [$\texttt{COCI 2009-2010}\ 2^\texttt{nd}\ \texttt{round}\ \text{T4 VUK}$](https://hsin.hr/coci/archive/2009_2010/contest2_tasks.pdf)。 The scoring follows the original problem, with a full score of $100$。

A wolf, Vjekoslav, is fleeing from a group of brutal hunters. These hunters are very cruel and often hide behind trees, but Vjekoslav does not know which tree has a hunter behind it. To be safe, Vjekoslav wants to stay as far away from trees as possible while escaping back to its comfortable den. The forest can be modeled as an $N \times M$ matrix. Each cell may be empty (denoted by `.`), or it may have a tree at its center (denoted by `+`). Vjekoslav is at the position marked `V`, and its den is at the position marked `J`. Define the distance between Vjekoslav and a tree as the Manhattan distance between their cells (i.e., the sum of the absolute differences of their row and column indices). At each step, Vjekoslav can move one cell in any of the four directions: east, south, west, or north, **even if the next cell contains a tree (in this problem, trees do not block Vjekoslav)**. Help find a path from `V` to `J` such that the minimum distance from Vjekoslav to the nearest tree along the path is as large as possible. **Note that Vjekoslav’s den does not occupy the entire cell, so your path must include `J`.**

The first line contains two integers $N, M$。 The next $N$ lines each contain $M$ characters describing the forest。 In the forest description, there is exactly one `V` and one `J`, and it is guaranteed that there is at least one `+`。

Output one integer: the maximum possible value of the minimum distance from Vjekoslav to the nearest tree along the route back to the den。

$1 \leq N, M \leq 500$。 Translated by ChatGPT 5