walk

题目描述

给出一个 $n \times m$ 的矩阵，起点用 'V‘ 来表示，终点用 'J' 来表示，'.' 代表没有敌人的地方，'+' 代表有敌人的地方，求从起点走到终点的所有路径中，距离敌人距离最近距离最远的路径是多少。

距离敌人的最近距离指的是路径上任何一个点和任何一个敌人位置的最近距离

此处距离定义为曼哈顿距离，$dis[(i,j),(k,l)]=|i-k|+|j-l|$

输入格式

第一行两个整数 $n,m$ 代表矩阵大小

$n$ 行每行 $m$ 个字符，一个 'V' 一个 'J' ，其余为 '.' 或者 ‘+’（保证至少有一个 '+' )

输出格式

一行一个整数（注意答案可能为0，即可以走到敌人在的位置上）

样例

样例输入 #1

8 8
V......+
......+.
.....+..
....+...
........
........
........
+......J

样例输出 #1

3

数据范围

对于20%的数据，$1\le n,m\le 20$

对于60%的数据，$1\le n \times m \le 20000$

对于100%的数据，$1\le n,m \le 500$