题目描述

Nemoarce这次在须弥参与解谜嬴原石的小游戏，这次他迎来的游戏是这样的。 游戏规定:Nemoarce需要进行多次滑动。每次滑动选择一个$P$作为自己的起点，从起点出发，并沿着一个方向(上下左右)前进，前进的同时需要保证

• 1.不能走到 N的格子上
• 2.不能走出mxn的地图
• 3.不能中途改变方向

当一次滑动结束时，Nemoarce可以开始选择下一个$P$并开始下一次滑动直到地图中不存在$P$,游戏结束。为了增加游戏的趣味性，每经过一个格子，这个格子就会从$P$变成 $N$。 米忽悠为了让游戏充满挑战性，进行的滑动的次数越少，得到的奖励越多.

现在Nemoarce想要拿到最高等级的奖励，来抽取小吉祥草王，所以他把地图交给了你，请你好好研究下怎么解决这个问题。

输入格式

第一行两个数字$m，n$表示正方形地图的边长

接下来$m$行，每行1个长度为$n$的字符串，由$P$和 $N$组成。

输出格式

一行一个数字，表示最少需要的滑动次数。

样例

6 6
PPPPPP
PPNNNN
PPPPPP
PPNNNP
PPNNNP
PPPPPP

6

数据范围

$0 < m,n \leqslant 200$

来源

Ianysure