NAGAY1 - VUK

Vjekoslav the Wolf is running away from a bunch of blood hungry hunters. The hunters are smart and hide behind trees. Vjekoslav knows this, but doesn't know which trees. He would like to run to his comfortable, civilized cottage (as opposed to the hunters quite uncivilized den, yes I am rooting for the Wolf here) staying as far away as possible from any trees.

The forest can be represented as a N by M gird. Let us mark empty meadow patches with '.', patches with a tree in the middle with '+', Vjekoslav's current position with 'V' and the position of his cottage with 'J'. Vjekoslav can run from his current patch to any other patch north, east, south or west from him, even if it contains a tree.

If Vjekoslav is standing in R-th row and C-th column on the grid and there is a tree in the A-th row and B-th column then the distance between Vjekoslav and that tree is:

|R-A| + |C-B|

Help Vjekoslav find the best route to his cottage. The best route is any route that maximizes the minimal distance between Vjekoslav and all trees at any given moment. Note that Vjekoslav's cottage doesn't occupy the entire patch so that patch must also be included in the route.

Input

The first line of input contains integers N and M (1 ≤ N, M ≤ 500), grid dimensions. The next N lines contain M characters each: '.', '+', 'V', 'J'. Input will contain exactly one character 'V' and 'J' and at least one character '+'.

Output

Output a single integer, the minimal distance from a tree in the optimal route.

Example

Input:
4 4
+...
....
....
V..J

Output:
3

Added by:Azat Taryhchiyev
Date:2012-02-17
Time limit:0.100s
Source limit:30000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:ASM32-GCC MAWK BC C-CLANG NCSHARP C++ 4.3.2 CPP CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JS-MONKEY JULIA KTLN NIM NODEJS OBJC OBJC-CLANG OCT PAS-GPC PAS-FPC PICO PIKE PROLOG PYPY PYPY3 PY_NBC R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET
Resource:2011 KRSU School Contest [olymp.krsu.edu.kg]

hide comments
2018-12-21 03:03:13
Turns out that despite silly TL it's actually solvable in Python as judge doesn't seem to test against extreme cases. It was fun to remember the futile struggle a 10 months younger version of me had here and find out that an elegant solution can be easily put together from two other very good problems I had solved in the meantime.

Careful with SPOJ Toolkit on this one, for cases like:
+++
V.J
+++
.. the answer is of course 1 not 0.
2018-08-20 11:29:17
nice problem

Last edit: 2018-08-20 15:53:00
2018-08-20 08:40:52
suka bljet
2012-03-12 07:07:14 :D
Yes
2012-02-23 09:26:54 Raziman T V
Should the minimum distance to the trees from the start and end point be considered as well?
2012-02-19 08:38:34 Buda IM (retired)
Resource is COCI
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.