一匹狼 Vjekoslav 正在逃离一批残暴的猎人的追捕。
这些猎人非常凶残,经常躲在树后面,但 Vjekoslav 并不知道哪棵树后有猎人。为了保险,Vjekoslav 希望在逃回它舒适的窝的过程中离树越远越好。
森林可以抽象为 N\times M 的矩阵。每个格子可能是空的(用.表示),也有可能有一棵树在中心位置(用+表示)。Vjekoslav在V标示的地方而它的窝在J标示的地方。定义 Vjekoslav 与某棵树的距离为它们所在格的曼哈顿距离(即这两个格子所在行、列之差的绝对值之和)。
Vjekoslav 每次可以往东南西北中的任一方向移动,即使它下一步移动到的格子有树(此题树并不会阻挡 Vjekoslav)。帮忙找出这样一条从V到J的路径,使得 Vjekoslav 在途中离它最近的树的距离的最小值最大。
注意 Vjekoslav 的窝并不占据整块格子,因此你的路径中必须包含J。